Finding Zen in the Art of Puzzle Solving
The “eureka” or “aha” moment of insight is legendary in math and science, dating at least two millenniums back to the possibly apocryphal story of Archimedes rushing naked out of a bath, having hit upon the crucial idea for figuring out the composition of King Hiero’s crown. Many scientific discoveries have been credited to such moments, from Newton’s theory of gravity to Einstein’s. These “aha” insights often seem to emerge from a calm, Zen-like state, in which you’re not directly addressing the problem but it’s floating around in your mind.
But the problem needs to cooperate too. Many math and science problems require long, hard calculations, but some lend themselves to insight-given solutions. In these rare cases, a fresh perspective can suddenly provide clarity, reducing complexity to simplicity in a convincing and memorable way. Puzzles 1 and 3 from last month’s Insights column were of this type, while Puzzle 2 only seemed to be — a simple, clear resolution remained elusive. Let’s look at the easier pair first. In each case we will use a Zen-like aphorism which can be linked to a specific mathematical solving technique.
Puzzle 1: The Zen of the Frenzied Ants
- Imagine a narrow twig spanning two mounds on an anthill to form a bridge 100 inches long. There are 10 ants on the twig, evenly spaced from the left end (let’s call this coordinate 0) to close to the right end (coordinate 90). You can ignore the lengths of the ants themselves. The five ants on the left are facing right, and the five on the right are facing left. All of the ants start walking in the direction they are facing at a constant speed of 100 inches/minute. The twig is so narrow that when two ants meet, they turn around instantaneously and walk away from each other at the same speed, exhibiting the kind of frenzied behavior typical of ants. When an ant reaches the end of the twig, it descends to the mound it has reached. How long does it take for the twig to be free of ants?
- In the same setting as above, imagine there are 100 ants on the twig. There are 75 facing left and 25 facing right, each at an unknown location on the twig, randomly interspersed with one another. The ant at the far left faces right, and the rightmost ant, which is close to the end of the twig but not quite there, faces left. The ants all behave as described above and move at the same speed. Obviously, there are many more collisions and reversals of direction. Now how long will it take for the twig to be cleared?
- In scenario b, which is the last ant to leave the twig, and which way was it facing originally?
Follow the message, not the messenger.
You can easily solve these questions if you imagine the ants exchanging little notes every time they collide. For part a, the note that any individual ant was carrying originally will continue on its merry way in the same direction and at the same speed through every collision, albeit carried by different ants. By focusing on the messages and not the ants, you can replace the frenzied behavior of the ants themselves with the uniform linear motion of the notes. Every time a note reaches the end of the twig, it is carried off the twig, taking one ant with it. The note that has the longest to travel is the one sitting in the jaws of the ant at the left end of the twig, which will take one minute to reach the other end. It will carry the last ant (whichever one it turns out to be) off the twig. So the answer is one minute.
The same image works for part b. As you can see from part a, it doesn’t matter where the ants are on the twig or which direction they’re facing. The only thing that matters is: Which message has the longest distance to travel? The answer again is the one at the far left, which will again take one minute to be cleared from the twig.
The trick is to transform the problem into a different framework or coordinate system that eliminates the complexity.
Hold ye to what is constant.
For part c, you have to focus on a different truth. You have to remember that no matter how many collisions take place, the ants do not change places. The order of the ants on the twig never changes, because the ants cannot pass through or over each other. So if 25 messages were carried off the right end of the twig, the 25 rightmost ants had to have carried them, and the final message had to be carried by the 25th ant from the right end. Since the ants facing right or left started off randomly interspersed on the twig, this last ant could have been facing either direction originally.
The technique here is to look for what doesn’t change in a problem — the invariants — in spite of the underlying complexity.
Several readers solved at least parts of this problem, including Lord of Steel, Arnout Jaspers, Frank Louage, Vikas Kedia, Manuel Fortin, Alona Levy, Adrien, Federico Kereki, okfuture, Paolo Abiuso, Ian Wroe and Ashley Lopez, and some offered their insights as hints. Some helpful images that readers provided are to picture the ants as exchanging messages, or their souls or their inner Buddhas, or passing through each other like ghosts, or as being interchangeable, like bosons.
Puzzle 3: The Zen of Accepting the Empty Seat
You are invited to an event that has 100 assigned seats. You arrive last, but the person who arrived first, a VIP, did not have his assigned seat number and occupied some random seat that he liked. As the rest of the guests arrived, they took their assigned seats if they were unoccupied, or any arbitrary seat if not. Only one seat is left when you arrive. What is the chance that it is your assigned seat?
The mismatched guest says: “I could cut the chaos in two ways — if I were enlightened.”
Like the ant puzzle, this one seems to be full of complexity: On the surface, we have a domino effect of multiple seat changes. But look more closely and you’ll see a kind of invariant here: The number of unoccupied mismatched seats is always 1 or zero. Let’s number the assigned seats by the order of arrival of the guests. If the VIP, who should have been in seat 1, takes seat 13, it doesn’t affect anyone yet to come except guest 13. When this person arrives, she can stop further chaos by taking either seat 1 or seat 100. In either case there will be no further mismatched seats for the intermediate guests until you arrive, and then you will have a 1 in 2 chance of getting your assigned seat — depending on the choice that guest 13 made. If guest 13 takes some other seat — say, seat 20 — then the situation is similar to the one after the VIP sat down. Now it is guest 20 who can prevent further chaos by choosing seat 1 or 100, or prolong the situation by choosing another seat whose owner will make the next choice, and so on. If no one in this chain chooses seat 1 or 100, then guest 99 will make the final 50-50 decision.
Correct answers: Lord of Steel, Lazar Ilic, Paolo Abiuso, Federico Kereki, Ashley Lopez, Benjamin Adler.
Puzzle 2: Zen and the Art of Gambling
I invite you to a betting game played with cards. I’m the dealer. I charge you a fee for the privilege of playing, since the game is stacked in your favor and you have a positive expected winning amount with the best strategy. I then give you a pot of $100 to start the game, taken out of your entry fee. This pot may grow or shrink during the game depending on your ongoing wins or losses. You have to bet from this dynamic pot, and only from this pot — you cannot add anything else to it other than your winnings, which automatically go back into the pot.
I shuffle a regular deck of cards and put it facedown in front of you. You can make an even-money wager on whether the top card is black or red, betting any amount from zero up to the amount you currently have. Let’s say you bet $10 that the card is red. I then turn the card over. Depending on whether you are right or wrong, $10 is either added to your pot or taken away. Thus, if the card was black, you now have $90. If you then bet $20 dollars that the next card is black, and it is, you now have $110.
The game continues until all the cards are turned over, or your pot shrinks to zero. This means you have up to 52 chances to bet.
Obviously, once you know that the remaining cards are all of a certain color (you’re allowed to keep track of the flipped cards — I’m not a casino), you should bet the entire pot on the remaining color the rest of the way. But how do you bet before that point arrives? (Seven possible strategies were suggested in the puzzle column.)
After solving the ant puzzle, Lord of Steel commented, “It’s strange to think that had I not known there was some ‘insight’ involved, I may have never encountered the insight. I might have been stuck trying to work things out the long way the whole time.” Exactly! Unless you know to look for the insight, you have to start solving the problem any way that seems intuitively correct to you. As you do so and your brain absorbs the structure and patterns emerging from your effort, you may be blessed with an insight, or it may come when you are at a dead end, having hit a wall after a lot of hard effort.
Let’s look at Puzzle 2 and glean what partial insights we can. First, notice that what you’re looking for is a strategy that maximizes your “expected” value. In a single game you may win or lose, but that’s fine as long as the strategy is sound in the long run. Second, when there are equal numbers of black and red cards, your expectation for that round will be zero. Third, you will obviously make out big when all the remaining cards are the same color (that is, when the colors are maximally unbalanced), because you will double your pot each round. The earlier you reach this point, the more you stand to make.
From this, you know that your first-round bet, when the outstanding black and red cards are equal, won’t affect your expectation. In the second round, the obvious strategy is to bet on the more abundant color. Your probability of winning will be more than even. If you do win, the colors will be balanced again. But if, on the other hand, you bet on the less abundant color and win, then the colors will become even more unbalanced, potentially enhancing your winnings in the future. So even if your chances of winning this round are less than half, there may be some advantage in doing so.
And this is where the puzzle differs from standard probability problems where the probabilities and the amount available do not get reconfigured to make the worse choice pay off later. But what is the expected value of this benefit? Let’s find out.
Remember, building the most complex temple starts with the first brick.
At this point you can start calculating probabilities if you are fluent in the requisite mathematical tools, or you can try out a simpler version of the problem. Let’s do the latter. While doing so, we must make sure that the number is not so small that the problem becomes trivial, as it would be for two cards. So let’s try the problem for a deck of four cards.
The tables below show the expected value calculation for all the described strategies.
The first column lists all the six possible shuffles for four cards, each of which has a probability of 1/6. Each strategy is labeled in the second row and described in the third. Note that each strategy is followed as described until all remaining cards are the same color. The round at which this occurs is listed in the second column. The evolution of the pot is shown for each of the six possible card orders for four-card decks, with the final amount shown in red. All the possible final amounts are added up and divided by 6 to give the final expectation.
Incredibly, all the strategies give exactly the same expectation! This includes strategies that bet on the color that is less likely, and strategies that are cautious or reckless, or painstakingly thought out!
Is the universe like noise-canceling headphones?
You bet! At least, the universe of this problem is. No matter how noisy or complex the strategy you choose, the expectation is always the same. Notice that when the bet is doubled as in strategy 2 compared to strategy 1, the win is greater with a favorable shuffle, but that is precisely compensated for by a worse pot when the card order is the reverse (compare RRBB with BBRR, or RBRB with BRBR). The most reckless strategy wins a big jackpot for just one deck but nothing for all the others. The benefit of the unbalanced deck precisely, almost uncannily, balances the benefit of betting for the more abundant color. This insight, and the way to prove it, was first pointed out in the comments by Erik H, who correctly deduced that all strategies are equivalent, even those betting on the less probable color, as long as you bet the whole pot on the color that is left when the other one is exhausted. Paolo Di Giusto, Erik H and Paolo Abiuso derived the recurrence relation for the expectation, showing how the expected value changes based on its preceding value as a new card is turned — this is the first step to uncovering this mystery. Paolo Abiuso deduced from the recurrence relation that the advantage of the unbalanced deck created by the less probable color turning up would precisely balance the advantage of the more probable color turning up, rendering your bet irrelevant, if the following relationship is true:
m × E(m − 1, n) = n × E(m, n − 1)
where m and n are the number of red and black cards that are still left and E(m, n) is the expected value you will get when there are m red and n black cards. This relation remains the same whether you bet on the less probable or the more probable color. The way you can prove this for decks of all sizes is by the magic of mathematical induction. That is, you start out by showing the result is true for small numbers, as we did, and then show that if it works for a certain n, then it also has to work when a single card is added to the deck. Voila, it therefore works for all n. You can check out the actual expressions in Paolo Abiuso’s post.
Once you know that all strategies are equivalent, you can calculate the expected value for any of them. The easiest to calculate is the expectation for the reckless strategy where you bet on all the red cards first. The chance that you are right is the reciprocal of 52 choose 26, and your initial pot of 100 doubles every round, giving you a win of 100 × 252 dollars. The expression is
100 × 252(26!26!/52!),
which, as Wolfram Alpha will tell you, is $908.13, and that is the theoretical fair value for entry to the game (a standard casino would probably charge around $950). I say “theoretical fair value” because in actual fact you stand to win such an astronomical amount (~$450 quadrillion), if you get really, really lucky on a reckless bet, that you could never collect it. You’d have to settle for the scraps that a bankruptcy court would let you have as my creditor. This would no doubt lower the value of your expectation!
Others who provided proofs and/or correct calculations for the amount are Lazar Ilic, Muhaimin Khan, Charles Wang, Laurent, Valentin Vincendon, Manuel Fortin, Ashley Lopez and Okhtay Ilghami. Several readers pointed out that for large numbers the answer can be approximated by Stirling’s formula, which in one of those wonderful mathematical twists, uses π. One more reason to celebrate pi day!
The final probabilistic strategy that I used in the table above is the “no variance” strategy described by Laurent, which earns exactly the expected value for every deck. Kudos to Laurent for finding it and providing a proof!
Thank you to all who contributed solutions and insights. The prize for this month goes to Erik H. Congratulations!
See you next month for new Insights.
Correction: March 26, 2021
An error in reproducing the table in the solution to Puzzle 2 has been corrected. A typographical error has also been remedied to reflect that Stirling’s formula uses π, not “p.”
The post Finding Zen in the Art of Puzzle Solving first appeared on Quanta Magazine.