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

Still Life

In 2009 British artist Roger Hiorns won the Turner Prize by melting a passenger aircraft engine, pouring it through a funnel, and spraying it with water to break it into fine granules.

Its dimensions are listed as “variable.”

September 11, 2014September 10, 2014 | Art

Likewise

A charming little scene from mathematical history — in 1615 Gresham College geometry professor Henry Briggs rode the 300 miles from London to Edinburgh to meet John Napier, the discoverer of logarithms. A contemporary witnessed their meeting:

He brings Mr. Briggs up into My Lord’s chamber, where almost one quarter of an hour was spent, each beholding the other with admiration, before one word was spoke: at last Mr. Briggs began. ‘My Lord, I have undertaken this long journey purposely to see your person, and to know by what engine of wit or ingenuity you came first to think of this most excellent help unto Astronomy, viz. the Logarithms: but my Lord, being by you found out, I wonder nobody else found it before, when now being known it appears so easy.’

Their friendship was fast but short-lived: The first tables were published in 1614, and Napier died in 1617, perhaps due to overwork. In his last writings he notes that “owing to our bodily weakness we leave the actual computation of the new canon to others skilled in this kind of work, more particularly to that very learned scholar, my dear friend, Henry Briggs, public Professor of Geometry in London.”

September 11, 2014September 10, 2014 | History · Science & Math

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 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 21, 2014 | Puzzles

Self-Test

leder patent

Xavier Henry Leder, who declares himself “by profession a seaman,” patented this “foul breath indicator” in 1902, perhaps after inventing it for his own use.

“It is an appliance in the shape of a tube, made of any non-absorbent material and curved so as to transmit without any obstruction the breath from the mouth to the nostrils. … By breathing from the mouth through the tube any foulness or unpleasant state of the breath may be readily detected by the sense of smell.”

The hard part is exhaling and inhaling at the same time.

September 10, 2014September 9, 2014 | Technology

Unquote

“The greatest deception men suffer is from their own opinions.” — Leonardo

“Convictions are more dangerous enemies of truth than lies.” — Nietzsche

“Opinions have caused more ills than the plague or earthquakes on this little globe of ours.” — Voltaire

“The most difficult subjects can be explained to the most slow-witted man if he has not formed any idea of them already; but the simplest thing cannot be made clear to the most intelligent man if he is firmly persuaded that he knows already, without a shadow of doubt, what is laid before him.” — Tolstoy

“Nothing is so firmly believed as that which we least know.” — Montaigne

“Opinions are made to be changed, or how is truth to be got at?” — Lord Byron

“Nothing is more conducive to peace of mind than not having any opinions at all.” — G.C. Lichtenberg

September 10, 2014September 9, 2014 | Quotations

Encounter

We had a dark grey cat (Norfolk bred, very Norfolk in character) called Tom. He was reserved, domineering, voluptuous — much as I imagine Tiber to be. When he was middle-aged he gave up nocturnal prowlings and slept on my bed, against my feet. One evening I was reading in bed when I became aware that Tom was staring at me. I put down my book, said nothing, watched. Slowly, with a look of intense concentration, he got up and advanced on me, like Tarquin with ravishing strides, poised himself, put out a front paw, and stroked my cheek as I used to stroke his chops. A human caress from a cat. I felt very meagre and ill-educated that I could not purr. It had never occurred to me that their furry love develops from what was shown them as kittens.

— Sylvia Townsend Warner, letter to David Garnett, June 18, 1973, quoted in The Oxford Book of Friendship

September 9, 2014September 9, 2014 | Literature

A Magic Jigsaw

https://commons.wikimedia.org/wiki/File:Geomagic_square_-_Magic_Jigsaw.jpg — Image: Wikimedia Commons

A “self-interlocking” geomagic square by Lee Sallows. The 16 lettered pieces pave a single large square, and smaller squares can be produced by various groups of four pieces — those drawn from each row, column, and long diagonal, and 10 other symmetrically chosen quartets.

September 9, 2014September 9, 2014 | Science & Math