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.
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.”
Canadian doctor Samuel Bean created a curious tombstone for his first two wives, Henrietta and Susanna, who died in succession in the 1860s and are buried side by side in Rushes Cemetery near Crosshill, Wellesley Township, Ontario. The original stone weathered badly and was replaced with this durable granite replica in 1982. What does it say?
You’re a logician who wants to know which of two roads leads to a village. Standing nearby, inevitably, are three natives: one always lies, one always tells the truth, and one answers randomly. You don’t know which is which, and you can ask only two yes-or-no questions, each directed to a single native. How can you get the information you need?
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.)
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?
From the Second All Soviet Union Mathematical Competition, Leningrad 1968:
On a teacher’s desk sits a balance scale, on which are a set of weights. On each weight is the name of at least one student. As each student enters the classroom, she moves all the weights that bear her name to the other side of the scale.
Before any students enter, the scale is tipped to the right. Prove that there’s some set of students that you can let into the room that will will tip the scale to the left.
Two circles intersect. A line AC is drawn through one of the intersection points, B. AC can pivot around point B — what position will maximize its length?
A puzzle by Pierre Berloquin:
Timothy, Urban, and Vincent are digging identical holes in a field.
- When Timothy and Urban work together, they dig 1 hole in 4 days.
- When Timothy and Vincent work together, they dig 1 hole in 3 days.
- When Urban and Vincent work together, they dig 1 hole in 2 days.
Working alone, how long does it take Timothy to dig one hole?
On Oct. 25, 1875, Lewis Carroll sent this verse to Mrs. J. Chataway, mother of one of his child-friends, Gertrude. “They embody, as you will see, some of my recollections of pleasant days at Sandown”:
Girt with a boyish garb for boyish task,
Eager she wields her spade — yet loves as well
Rest on a friendly knee, the tale to ask
That he delights to tell.
Rude spirits of the seething outer strife,
Unmeet to read her pure and simple spright,
Deem, if you list, such hours a waste of life,
Empty of all delight!
Chat on, sweet maid, and rescue from annoy
Hearts that by wiser talk are unbeguiled!
Ah, happy he who owns that tenderest joy,
The heart-love of a child!
Away, fond thoughts, and vex my soul no more!
Work claims my wakeful nights, my busy days:
Albeit bright memories of that sunlit shore
Yet haunt my dreaming gaze!
He asked her leave to have it published. The child in the verse is not named — why should he feel obliged to ask permission?
You’re standing in a room with an uneven floor. Before you is a square table with four legs. The table wobbles, but by turning it gradually you manage to find a position in which all four feet are supported, eliminating the wobble (though now the tabletop isn’t level).
You wonder: Is this always possible? Assuming that the four legs are of equal length and that the surface of the floor varies smoothly, is it always possible to position a four-legged table so that all four legs are supported?
Three positions, “left,” “middle,” and “right,” are marked on a table. Three cards, an ace, a king, and a queen, lie face up in some or all three of the positions. If more than one card occupies a given position then only the top card is visible, and a hidden card is completely hidden; that is, if only two cards are visible then you don’t know which of them conceals the missing card.
Your goal is to have the cards stacked in the left position with the ace on top, the king in the middle, and the queen on the bottom. To do this you can move one card at a time from the top of one stack to the top of another stack (which may be empty).
The problem is that you have no short-term memory, so you must design an algorithm that tells you what to do based only on what is currently visible. You can’t recall what you’ve done in the past, and you can’t count moves. An observer will tell you when you’ve succeeded. Can you devise a policy that will meet the goal in a bounded number of steps, regardless of the initial position?
“It’s tricky to design an algorithm that makes progress, avoids cycling, and doesn’t do something stupid when it’s about to win,” wrote Dartmouth mathematician Peter Winkler in sharing this puzzle in his book Mathematical Puzzles: A Connoisseur’s Collection (2003). It’s called “The Conway Immobilizer” because it originated with legendary Princeton mathematician John H. Conway and because it’s said to have immobilized one solver in his chair for six hours.
A man presents himself as the The Amazing Sand Counter. He claims that if you put some quantity of sand into a bucket, he will know at a glance how many grains there are, but he won’t tell you the number. Can you devise a test that can verify this ability without telling you anything that you don’t already know? You can ask the Sand Counter to leave the room or turn away, for example, and you can ask him questions. How can you convince yourself that he knows how many grains of sand are in the bucket when he won’t actually tell you the number?
A mother is 21 years older than her son. Six years from now, she will be five times his age. Where’s the father?
I won’t give the answer to this one — if you do the math, you’ll know precisely where he is.
From Stephen Barr’s Experiments in Topology (1989) via Miodrag Petkovic’s Mathematics and Chess (1997):
This apartment contains eight rooms, each measuring 9 square meters, except for the top one, which measures 18 square meters. You have enough red paint to cover 27 square meters, enough yellow paint to cover 27 square meters, enough green paint to cover 18 square meters, and enough blue paint to cover 9 square meters. Can you paint the eight floors in four colors so that each room neighbors rooms of the other three colors?
Can two dice be weighted so that the probability of each of the numbers 2, 3, …, 12 is the same?
A bisecting arc is one that bisects the area of a given region. “What is the shortest bisecting arc of a circle?” Murray Klamkin asked D.J. Newman. Newman supposed that it was a diameter. “What is the shortest bisecting arc of a square?” Newman answered that it was an altitude through the center. Finally Klamkin asked, “And what is the shortest bisecting arc of an equilateral triangle?”
“By this time, Newman had suspected that I was setting him up (and I was) and almost was going to say the angle bisector,” Klamkin writes. “But he hesitated and said let me consider a chord parallel to the base and since this turns out to be shorter than an angle bisector, he gave this as his answer.”
Was he right?
A and B are playing a simple game. Between them are nine tiles numbered 1 to 9. They take tiles alternately from the pile, and the first to collect three tiles that sum to 15 wins the game. Does the first player have a winning strategy?
A conduit carries 50 identical wires under a river, but their ends have not been labeled — you don’t know which ends on the west bank correspond to which on the east bank. To identify them, you can tie together the wires in pairs on the west bank, then row across the river and test the wires on the east bank to discover which pairs close a circuit and are thus connected.
Testing wires is easy, but rowing is hard. How can you plan the work to minimize your trips across the river?