Warnsdorff’s Rule

The knight’s tour is a familiar task in chess: On a bare board, find a path by which a knight visits each of the 64 squares exactly once. There are many solutions, but finding them by hand can be tricky — the knight tends to get stuck in a backwater, surrounding by squares that it’s already visited. In 1823 H.C. von Warnsdorff suggested a simple rule: Always move the knight to a square from which it will have the fewest available subsequent moves.

This turns out to be remarkably effective: It produces a successful tour more than 85% of the time on boards smaller than 50×50, and more than 50% of the time on boards smaller than 100×100. (Strangely, on a 7×7 board its success rate drops to 75%; see this paper.) The video above shows a successful tour on a standard chessboard; here’s another on a 14×14 board:

While we’re at it: British puzzle expert Henry Dudeney once set himself the task of devising a complete knight’s tour of a cube each of whose sides is a chessboard. He came up with this:


If you cut out the figure, fold it into a cube and fasten it using the tabs provided, you’ll have a map of the knight’s path. It can start anywhere and make its way around the whole cube, visiting each of the 364 squares once and returning to its starting point.

Dudeney also came up with this puzzle. The square below contains 36 letters. Exchange each letter once with a letter that’s connected with it by a knight’s move so that you produce a word square — a square whose first row and first column comprise the same six-letter word, as do the second row and second column, and so on.

dudeney knight's tour word square puzzle

So, for example, starting with the top row you might exchange T with E, O with R, A with M, and so on. “A little thought will greatly simplify the task,” Dudeney writes. “Thus, as there is only one O, one L, and one N, these must clearly be transferred to the diagonal from the top left-hand corner to the bottom right-hand corner. Then, as the letters in the first row must be the same as in the first file, in the second row as in the second file, and so on, you are generally limited in your choice of making a pair. The puzzle can therefore be solved in a very few minutes.”

Click for Answer

Different Strokes


G.H. Hardy had a famous distaste for applied mathematics, but he made an exception in 1945 with an observation about golf. Conventional wisdom holds that consistency produces better results in stroke play (where strokes are counted for a full round of 18 holes) than in match play (where each hole is a separate contest). So if two players complete a full round with the same total number of strokes, then the more erratic player should do better if they compete hole by hole.

Hardy argues that the opposite is true. Imagine a course on which every hole is par 4. Player A is so deadly reliable that he shoots par on every hole. Player B has some chance x of hitting a “supershot,” which saves a stroke, and the same chance of hitting a “subshot,” losing a stroke. Otherwise he shoots par. Both players will average par and will be equal over a series of full rounds of golf, but the conventional wisdom says that B’s erratic play should give him an advantage if they play each hole as a separate contest.

Hardy’s insight is that the presence of the hole limits a run of good luck, while there’s no such limit on a run of bad luck. “To do a three, B must produce a supershot at one of his first three strokes, while he will take a five if he makes a subshot at one of his first four. He will thus have a net expectation 4x – 3x of loss on the hole, and should lose the match, contrary to common expectation.”

In general he finds that B’s chance of winning a hole is 3x – 9x2 + 10x3, and his chance of losing is 4x – 18x2 + 40x3 – 35x4, so that there’s a balance f(x) = x – 9x2 + 30x3 – 35x4 against him. If x < 0.37 -- that is, in all realistic cases -- the erratic player should lose. "If experience points the other way -- and I cannot deny it, since I am no golfer -- what is the explanation? I asked Mr. Bernard Darwin, who should be as good a judge as one could find, and he put his finger at once on a likely flaw in the model. To play a 'subshot' is to give yourself an opportunity of a 'supershot' which a more mechanical player would miss: if you get into a bunker you have an opportunity of recovering without loss, and one which you are naturally keyed up to take. Thus the less mechanical player's chance of a supershot is to some extent automatically increased. How far this may resolve the paradox, if it is one, I cannot say, and changes in the model make it unpleasantly complex." (G.H. Hardy, "A Mathematical Theorem About Golf," Mathematical Gazette, December 1945.)

All Right Then

W.H. Auden won first prize for mathematics at St. Edmund’s School in Hindhead, Surrey, when he was 13. He recalled being asked to learn the following mnemonic around 1919:

Minus times Minus equals Plus;
The reason for this we need not discuss.

Math Notes

1 + 2 = 3
1×2 + 2×3 + 3×4 = 4×5
1×2×3 + 2×3×4 + 3×4×5 + 4×5×6 = 5×6×7
1×2×3×4 + 2×3×4×5 + 3×4×5×6 + 4×5×6×7 + 5×6×7×8 = 6×7×8×9

In general, the sum of the first (n+1) products of consecutive n-tuples of consecutive integers is equal to the product of the next n-tuple.

(Thanks, Peter.)

Montmort’s Theorem

Suppose n students are sitting at n desks in a classroom. They’re asked to stand, mill around at random, and then sit again. What is the probability that at least one student will find herself in her original seat?

Intuition says that the probability ought to drop as the number of students increases, but in fact it remains about the same:

montmort table

In fact, Pierre Rémond de Montmort showed in 1708 that it’s

montmort theorem

… which approaches 1 – 1/e, or about 0.63212. Whether there are 10 students or 10,000, the chance that at least one student returns to her own seat is about 2/3.

Coming to Terms

Antoni Zygmund once asked if the World Series shouldn’t be called the World Sequence? And shouldn’t a combination lock be called a permutation lock? John Von Neumann once had a dog called Inverse. It would sit when told to stand and go when it was told to come. Von Neumann pronounced the term infinite series as infinite serious.

— Michael Stueben, Twenty Years Before the Blackboard, 1998



Starting in the 1970s, neurobiologist Otto-Joachim Grüsser spent 10 years collating the light sources in 2,124 paintings selected at random from Western art originating between the 14th and 20th centuries. He found that in most paintings considered Western works of art, especially those painted around the time of the Scientific Revolution, the light falls from the left.

“At the beginning of modern Western art during the early Gothic period, a preference for diffuse illumination or light sources distributed around the painted scene was found,” Grüsser noted. “In a minority of paintings from the fourteenth century that show a clear light direction, a bias to the left side is present. This left-sided preference increased at the expense of diffuse or middle light sources up to the sixteenth and seventeenth centuries and declined thereafter. In the twentieth century, the diffuse or middle type of light distribution again became dominant.”

It’s not clear what to make of this. It seems reasonable that a right-handed artist might favor light falling from the left, but why should this vary with time? Grüsser found that the left-handed Leonardo da Vinci applied light sources from varying angles, and Hans Holbein the Younger, also a dominant left-hander, favored light falling from the right.

“From such observations in the works of these two left-handed painters who painted, drew, and wrote with the left hand, one gains the impression that the distribution of left, middle, and right light direction in left-handed painters deviates significantly from the average distribution of light found in the paintings of other contemporary painters. It would be interesting to study the drawings and paintings of other confirmed left-handed artists, who worked exclusively with the left hand.”

(Otto-Joachim Grüsser, Thomas Selke, and Barbara Zynda, “Cerebral Lateralization and Some Implications for Art, Aesthetic Perception, and Artistic Creativity,” in Ingo Rentschler, Barbara Herzberger, and David Epstein, Beauty and the Brain, 1988.)

Hot and Cold

Suppose you have three identical Dewar flasks labeled A, B, and C. (A Thermos is a Dewar flask.) You also have an empty container labeled D, which has thermally perfect conducting walls and which fits inside a Dewar flask.

Pour 1 liter of 80°C water into flask A and 1 liter of 20°C water into flask B. Now, using all four containers, is it possible to use the hot water to heat the cold water so that the final temperature of the cold water is higher than the final temperature of the hot water? How? (You can’t actually mix the hot water with the cold.)

Click for Answer

A Dice Puzzle

Timothy and Urban are playing a game with two six-sided dice. The dice are unusual: Rather than bearing a number, each face is painted either red or blue.

The two take turns throwing the dice. Timothy wins if the two top faces are the same color, and Urban wins if they’re different. Their chances of winning are equal.

The first die has 5 red faces and 1 blue face. What are the colors on the second die?

Click for Answer