The Conway Immobilizer

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.

	Select Click for Answer
If there’s an empty slot, move a card to the right (“around the corner,” if necessary) to fill it. Exception: If the position is king-blank-ace or king-ace-blank, place the ace on the king. If all three cards are visible, move the card to the right of the queen one space to the right (again, “around the corner” if necessary). Exception: If the queen is on the left, place the king on the queen. “Amazingly, the algorithm can be generalized to work with any (fixed, known) number of cards, still in three stacks,” Winkler writes. See his book for a five-rule algorithm that will reliably sort a 52-card deck.

Click for Answer

September 12, 2014September 21, 2014 | Puzzles

The Amazing Sand Counter

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?

	Select Click for Answer
This is from Dennis Elliott Shasha’s 1992 book Codes, Puzzles, and Conspiracy, via Barry Cipra’s 2004 collection Tribute to a Mathemagician. Shasha wanted to find the simplest possible zero-knowledge proof — a proof in which a Prover convinces a Verifier that the Prover knows something without ever revealing the thing itself. Shasha’s solution is this: Fill the bucket with sand, display it to the Sand Counter, then ask him to leave the room. Remove some countably small number of grains. When the Sand Counter returns, ask him how many grains have been removed from the bucket. Then count the removed grains to verify this. “The Verifier can repeat this test until he is convinced that the Sand Counter is either incredibly lucky (zero-knowledge proofs are often probabilistic in nature) or is telling the truth,” Shasha writes. This actually works both ways — it also convinces the Sand Counter that the Verifier knows the total number of grains in the bucket, even though he has never revealed it. “The Sand Counter is happy to answer these questions as long as the number of grains removed is tiny compared to the number in the bucket,” Shasha writes. “This way he can be sure that the Verifier has learned how many grains there are.”

Click for Answer

September 11, 2014September 6, 2024 | Puzzles

Where’s the Father?

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.

September 8, 2014September 7, 2014 | Puzzles

A Painting Conundrum

painting conundrum

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?

	Select Click for Answer
The task can’t be done with the colors given, but there’s a trick: If you mix 1/3 of the red paint into the blue paint you’ll produce enough purple paint to cover 18 square meters. And now a solution is possible:

September 7, 2014September 14, 2014 | Puzzles

Black and White

shinkman chess problem

By William Anthony Shinkman. White to mate in two moves.

	Select Click for Answer
The quiet 1. h6! forces 1. … Ng6 2. Qc4#.

September 5, 2014September 14, 2014 | Puzzles

Equal Opportunity

Can two dice be weighted so that the probability of each of the numbers 2, 3, …, 12 is the same?

	Select Click for Answer
I think this problem was first proposed by J.B. Kelly in the American Mathematical Monthly in 1950. The answer is no. Let a_j and b_j be the probabilities that the number j turns up on each of the two dice, and let P_j be the probability of getting the sum j on the pair of dice. So P₂ = a₁b₁ = a₆b₆ = P₁₂. Now, to maintain this balance, if the first die favors 1 over 6, then the second must favor 6 over 1, and vice versa, so that (a₁ – a₆)(b₁ – b₆) ≤ 0. But this means that P₂ + P₁₂ = a₁b₁ + a₆b₆ ≤ a₁b₆ + a₆b₁ ≤ P₇. The probabilities of rolling a 2, a 7, and a 12 cannot be equal.

Click for Answer

August 27, 2014September 7, 2014 | Puzzles · Science & Math

Black and White

By Francis Healey. White to mate in two moves.

	Select Click for Answer
1. Be5! and the queen will mate. From A Collection of Two Hundred Chess Problems, 1866.

August 23, 2014August 31, 2014 | Puzzles

Half and Half

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?

	Select Click for Answer
“Unfortunately for him, the correct answer is a 60° arc of a circle.” Reflect the triangle about successive bases to make a regular hexagon. Now we need a figure that occupies half the hexagon’s area and has the shortest possible perimeter. That’s a circle: “Incidentally, it is a very rare occasion when I can catch Newman on problems such as these.” From Klamkin’s paper “Mathematical Creativity in Problem Solving and Problem Proposing II,” in Joby Milo Anthony, ed., In Eves’ Circles, 1994, citing George Pólya’s Mathematics and Plausible Reasoning, 1954.

Click for Answer

August 22, 2014August 31, 2014 | Puzzles · Science & Math

Change of Venue

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?

	Select Click for Answer
No. Arrange the numbers into a magic square: 8 1 6 3 5 7 4 9 2 Now A and B are playing tic-tac-toe! And, hence, best play always leads to a draw. From Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, vol. 2, 2001.

August 19, 2014August 24, 2014 | Puzzles

The Wire Identification Problem

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?

	Select Click for Answer
Suppose the wires are labeled W₁, W₂, etc., on the west bank and E₁, E₂, etc. on the east bank. Start by tying W₁ to W₂, W₃ to W₄, and so on, leaving W₄₉ and W₅₀ untied. Now row across the river and test the wires to see which are connected. We might find that E₁₆ is tied E₃₇, E₁₁ is tied E₂₆, E₇ is tied E₄₁, and E₁₉ and E₂₇ are unconnected. Row back to the west bank, untie the wires, and now connect W₂ to W₃, W₄ to W₅, and so on, leaving W₁ and W₅₀ unconnected. Now return to the east bank and test again. We might learn that E₄₁ is tied E₁₉, E₂₆ is tied E₇, E₃₇ is tied E₁₁, and E₁₆ and E₂₇ are unconnected. Happily, we can now deduce all the connections. There will be one wire that had been paired in our first test but not in our second — here that’s E₁₆. That wire corresponds to W₁. The wire that E₁₆ had been paired with in our first test, E₃₇, must then correspond to W₂. And E₃₇ is now connected to E₁₁, so E₁₁ must be W₃. And so on: We can work down the list from W₁, alternately consulting the current connections and our memory of the first connections to reveal each wire in succession. So only three rowings are necessary. From Roland Sprague, Recreation in Mathematics, 1963. Sort of related: There’s a light bulb in the attic, and you’re downstairs facing three on-off switches. How can you tell which switch controls the light with only a single trip to the attic? Turn on Switch 1, leave it on for a minute, then turn it off, turn on Switch 2, and run upstairs. If the bulb is on, then Switch 2 controls it. If the bulb is off and warm (ha!), then Switch 1 controls it. Otherwise it’s Switch 3.

Click for Answer

August 17, 2014February 22, 2021 | Puzzles