## Head Games

Or how about this amazing result. Each of a million men puts his hat into a very large box. Every hat has its owner’s name on it. The box is given a good shaking, and then each man, one after the other, randomly draws a hat out of the box. What’s the probability that at least one of the men gets his own hat back? Most people would answer with ‘pretty slim,’ but in fact the answer is the astonishingly large 0.632! Who would have guessed that?

— Paul J. Nahin, *Will You Be Alive 10 Years From Now?*, 2014

## The Hydra Game

Hercules is battling a hydra. He manages to sever a head, but finds that a new head is generated according to the following rule: We move down one segment from the point where the head was severed and make a copy of the entire subtree above that point. Worse, the rate is increasing — the *n*th stroke of Hercules’ sword produces *n* new subtrees.

What will happen? The situation certainly looks dire, but, amazingly, Hercules cannot lose. No matter how large the hydra is, and no matter the order in which he severs the heads, he will always kill the hydra in finitely many turns.

Why? With each step, the complexity in the network is migrating toward the root — and that can’t continue forever. “We basically say that whenever something goes on *K* steps away from the root, it’s infinitely times worse than anything that is going on *K*-1 steps away from the root,” Comenius University computer scientist Michal Forišek explains in *Slate*.

“Now, whenever you kill a head, you very slightly simplified something that is *K* steps away. And even though you get a lot of new stuff in return, all that stuff is only *K*-1 steps away, and hence the entire result is still simpler than it was before.”

(Laurie Kirby and Jeff Paris, “Accessible Independence Results for Peano Arithmetic,” *Bulletin of the London Mathematical Society* 14 [1982], 285-293.)

## In a Word

idoneous

adj. apt, fit, or suitable

tripudiary

adj. pertaining to dancing

Hermit crabs adopt other creatures’ castoff shells for protection. But as they grow, crabs must move into successively larger shells. This produces a curious phenomenon: When a crab finds a shell that’s too big for it, it waits nearby. Other crabs may accumulate, forming a little conga line of dissatisfied shell seekers. Finally a “Goldilocks” crab arrives — a crab large enough to claim the new shell — and now each waiting crab can move into the shell abandoned by its larger neighbor. By cooperating to share a scarce resource, the whole species benefits.

The same thing happens in human societies — when one person finds a new apartment, car, or job, she leaves behind her old one, and the vacancy passes down through society until the final unit is cast away or destroyed. It’s called a vacancy chain.

(Thanks, Duncan.)

## Easy Pi

Here’s a simple algorithm that Yoshiaki Tamura and Yasumasa Kanada used to calculate π to 16 million places. It’s based on Gauss’ study of the arithmetic-geometric mean of two numbers. “Instead of using an infinite sum or product, the calculation goes round and round in a loop,” writes David Wells in *The Penguin Dictionary of Curious and Interesting Numbers*. “It has the amazing property that the number of correct digits approximately doubles with each circuit of the loop.” Start with these values:

Then follow these instructions:

The last instruction prints the first approximation to π; then you loop up to the top and run through the instructions again.

Running through the loop just three times gives an approximation to π that’s already correct to 5 decimal places:

Loop 1: 2.9142135

Loop 2: 3.1405797

Loop 3: 3.1415928

And running the loop a mere 19 times gives π correct to more than 1 million decimal places.

## Paperwork

Three ancient problems are famously impossible to solve using a compass and straightedge alone: doubling the cube, trisecting an angle, and squaring the circle. Surprisingly, the first two of these can be solved using origami.

In the first, doubling the cube, we’re given the edge of one cube and asked to find the edge of a second cube whose volume is twice that of the first; if the first cube’s edge length is 1, then we’re trying to find . Begin by folding a square of paper into three equal panels (here’s how). Then draw up bottom corner P as shown above, so that it’s touching the top edge while the bottom of the first crease, Q, touches the second crease as shown. Now point P divides the top edge into two segments whose proportions are 1 and .

To trisect an angle, begin by marking the angle in one corner of a square (here’s it’s CAB). Make a horizontal fold, PP’, anywhere across the square. Then divide the space below this crease in half with another crease, QQ’. Fold the bottom left corner up so that corner A touches QQ’ (at A’) and P touches AC. Now A’AB is one-third of the original angle, CAB.

The first of these constructions is due to Peter Messer, the second to Hisashi Abe. Strictly speaking, each uses creases to produce a marked straightedge, which is not allowed in classical construction, but they’re pleasingly simple solutions to these vexing problems. There’s more at origami wizard Robert Lang’s website.

## A New Angle

I just ran across this in an old *Math Horizons* article — Andy Liu, vice president of the International Mathematics Tournament of the Towns, calls it “one all-time favorite geometric gem.” Given the four angles shown, compute angle CAD. “It sounds like a trivial exercise at first, and therein lies its charm.”

Liu doesn’t give the solution, but he does give a hint — I’ll put that in a spoiler box in case you want to work on the problem first.

## Square Routes

If you fit Pascal’s triangle into a grid, then each cell displays the number of distinct paths that lead to that cell from the upper left (assuming only rightward and downward movements and no backtracking).

So, above, the cell marked 4 in the second row, fourth column, can be reached in 4 ways: 1-1-1-4, 1-1-3-4, 1-2-3-4, and 1-2-3-4.

## Decisions

A man who enters a public restroom has to make a complex choice quickly. He wants to choose a urinal that maximizes his chances of maintaining privacy — that is, that minimizes the chance that someone will occupy a urinal next to him. Which choice is best?

Computer scientists Evangelos Kranakis and Danny Krizanc modeled a number of strategies: lazily choosing the closest urinal that provides privacy; tacitly cooperating in the decision with other men; maximizing one’s distance from other occupants; and making the choice randomly. Happily, their findings support the general intuition:

Our main conclusion is that when faced with the decision of what urinal to choose upon entering the men’s room, in order to maximize your privacy, you should probably choose the one furthest from the door if it is available and the one next to it is unoccupied. For a vast majority of the (what we consider) natural behaviors that men choosing urinals might follow, this choice is optimal.

Related: In 1984 Donald E. Knuth noticed that the toilet paper dispensers in Stanford’s computer science department hold two rolls of tissue, both of which are available for use. Suppose there are two sorts of people in the world, those who are disposed to draw from the larger roll and those who draw from the smaller roll, and that each user takes exactly one sheet from his favored roll. What’s the expected number of sheets remaining just after one of the two rolls has been emptied? Donald E. Knuth’s Toilet Paper Problem.

(Evangelos Kranakis and Danny Krizanc, “The Urinal Problem,” in Paolo Boldi and Luisa Gargano, eds., *Fun With Algorithms: 5th International Conference, Fun 2010, Iscia, Italy, June 2010: Proceedings*.)