Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-sized, and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout (chosen at random) in next week’s column. If you need a hint, you can try asking me nicely on Twitter.
From Larry Peranich, a rock-solid probability problem:
A geology museum in California has six different rocks sitting in a row on a shelf, with labels on the shelf telling what type of rock each is. An earthquake hits and the rocks all fall off the shelf. A janitor comes in and, wanting to clean the floor, puts the rocks back on the shelf in random order. The probability that the janitor put all six rocks behind their correct labels is 1/6!, or 1/720. But what are the chances that exactly five rocks are in the correct place, exactly four rocks are in the correct place, exactly three rocks are in the correct place, exactly two rocks are in the correct place, exactly one rock is in the correct place, and none of the rocks are in the correct place?
A classic and twisted wire puzzle from Markus Ziegler:
There are N wires leading from the top of a bell tower down to the ground floor. But as wires tend to do, these have become hopelessly tangled. Good thing the wires on the top floor are all labeled, from 1 to N. The wires on the bottom, however, are not. (In retrospect, somebody probably should have anticipated a tangle or two.)
You need to figure out which ground-floor wire’s end corresponds to which top-floor wire’s end. (The bulk of the wiring is hidden behind a wall, so you can’t simply untangle them.) On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not. Tying two wire ends together and using the circuit detector are both very quick and easy, but this is an old tower and there is no elevator. So, bring your pedometer.
What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?
Solution to last week’s Riddler Express
Congratulations to 👏 Rosanne Zarmer 👏 of Scottsdale, Arizona, winner of last week’s Express puzzle!
Some number of players, N, competed in a round-robin tennis tournament. A win was worth one point and a loss was worth zero points. Three of the players, A, B and C, played their matches such that A lost to B, B lost to C, and C lost to A. After the tournament was over, every player finished with a different number of points. Is this possible given the circular wins of A, B and C? Or was an error made by the official scorer?
Mistakes were made! Let’s prove this by first assuming that all N players had different scores, then searching for a contradiction. If all the players had different scores, those scores must be 0, 1, 2, … , and N-1. (N-1 is the max since you can’t beat yourself.) Clearly, every other player beat the player with zero points. Now, remove that bottom player from consideration. Then we can make a similar argument about the new bottom player, who finished with just one point: Everyone above him in the final standings beat him. (His only win was against the player with zero points.) And so on. Essentially, in this scenario, every player beat all the players ranked beneath him in the final tally.
Suppose, without loss of generality, that our players A, B and C, finished in that order in the final standings. Therefore, A must have beaten B and C. But this is a contradiction! That ranking would mean A couldn’t have lost to B, but our premise states that that’s exactly what happened. Therefore, mistakes were made in tallying the scores.
Solution to last week’s Riddler Classic
Congratulations to 👏 Anne Paulson 👏 of Los Altos, California, winner of last week’s Classic puzzle!
Two countries, call them A and B, with armies of randomly determined strengths somewhere between 0 (very weak) and 1 (very strong), are deciding whether or not to declare war on each other to win a stash of gold. Each country knows its own strength, but not that of the other. They declare “war” or “peace” simultaneously. If either declares war, they go to war, and the country with the stronger army wins. The optimal strategy? Always declare war!
Why? Suppose the optimal strategy is to declare war when your strength is greater than some number X and that, because each player is facing an identical situation at the beginning of the game, both players play according to this strategy. Here’s where the game theory comes in. If Country B declares war if and only if its strength is greater than X, Country A would do well to declare war whenever its strength is greater than X/2. Why? There are two cases: In those situations where B’s strength (unknown to A) is greater than X, it doesn’t make any difference what A does, since B will declare war and A will be forced to fight. But in those situations where B’s strength is less than X, A profits by lowering its threshold to X/2. In half of those scenarios, it will be stronger than B, win the war, and double its gold cache.
But if A is declaring war when its strength is greater than X/2, then B will do well to declare war when its strength is greater than X/4, but then A would do well to declare war when its strength is greater than X/8, and so on. It’s bloodshed all the way down. They don’t stop until they’re both declaring war in every situation. Put another way, the only equilibrium “threshold” strength is 0. The strengths are always greater than 0, so both countries will always declare war.
The extra credit question asked what would happen if the declarations were made sequentially, rather than simultaneously, and what would happen if winning the war was worth even more. It turns out neither makes any difference. Here’s why: Suppose Country A must declare first. If it declares war, it doesn’t matter what B does. But if it declares peace, it signals to B that its strength is low. So B will want to declare war in many of those situations. But if B did declare peace, A would have wanted to declare war, and so forth. So the optimal strategies collapse to always declaring war. And if the value of winning the war is increased from $2 trillion to $5 trillion, there are simply larger spoils at the end of the war, making declaring war even more attractive.
War. What is it good for? Nash equilibrium.
Want to submit a riddle?
Email me at firstname.lastname@example.org.