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-size 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 in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
It’s been awhile since we had a participatory Riddler, so this week I am putting the onus on you! The very crown of Riddler Nation lies in the balance. Consult your game theory textbooks in advance.
Riddler Express
A classic participatory game theory problem:
Submit a whole number between 1 and 1,000,000,000. I’ll take all those numbers and find the average submission. Whoever submits the number closest to 2/3 of the mean of all of the submitted numbers wins and shall receive the title of Median Marquess of Riddler Nation.
(To complicate your analysis — the first time we held this competition, the mean was 195,921,656. So whaddya think? Higher? Lower? The same? Good luck!)
Riddler Classic
The third edition of the Riddler Nation battle royale!
In a distant, war-torn land, there are 10 castles. There are two warlords: you and your archenemy. Each castle has its own strategic value for a would-be conqueror. Specifically, the castles are worth 1, 2, 3, …, 9, and 10 victory points. You and your enemy each have 100 soldiers to distribute, any way you like, to fight at any of the 10 castles. Whoever sends more soldiers to a given castle conquers that castle and wins its victory points. If you each send the same number of troops, you split the points. You don’t know what distribution of forces your enemy has chosen until the battles begin. Whoever wins the most points wins the war.
Submit a plan distributing your 100 soldiers among the 10 castles. Once I receive all your battle plans, I’ll adjudicate all the possible one-on-one matchups. Whoever wins the most wars wins the battle royale and is crowned king or queen of Riddler Nation!
For your strategizing benefit, you may of course consult Riddler Nation’s chosen attack distributions from the first and second sanctioning of this battle royale, which had the same rules. Adapt and conquer!
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Jon Kutasov ÑÑâÐ of Chicago, winner of last week’s Riddler Express!
Last week brought us face to face with an all-powerful supervillain. That villain, Thanos, could snap his fingers and destroy half of all the beings in the universe. (There are no spoilers for the new Avengers movie in this solution, don’t worry.) But what if there were 63 Thanoses (Thani?), each of whom snapped his fingers one time, one after the other? Out of 7.5 billion people on Earth, how many could we expect would survive? If there were N Thanoses, what would the survival fraction be?
So this was a teeny bit of a trick question. But who said dealing with supervillains wouldn’t be tricky.
One way to approach this problem was to assume that each Thanos did indeed snap. In this case, half the population would be destroyed 63 times in a row, leaving a remaining decimal of \((0.5)^{63}\), or about 0.0000000000000000001. Multiplying that by the population of 7.5 billion gives about 0.0000000008 expected people remaining. In other words, everyone on the planet is dead. (Full credit shall be awarded for this solution, as I am a benevolent leader of Riddler Nation and certainly no pedant.)
But … the puzzle did say that Thanos snaps would destroy half of all the beings in the universe, and that includes other Thanoses. In this case, the problem gets far more interesting. So how do we deal with self-destructing Thanoses?
In an act of self-preservation, some of Riddler Nation attacked the problem head on. By this route, the first Thanos snap will leave 31 Thanoses, the second will leave 15, the third will leave seven, the fourth will leave three, the fifth will leave one and the sixth will leave none, for six total snaps. In other words, we figure that six snaps is the most likely number of snaps before all the Thanoses are gone — which is true. Six snaps means \((0.5)^6\) or 1/64 of the population will survive, yielding an answer of about 117.2 million.
But this answer is wrong. Why? Six snaps is certainly the most likely outcome of this supervillainous digital onslaught, but we don’t yet know how many Thanoses are caught up in another Thanos’s snap. It will most likely take six snaps, but it could also take just one snap or 10 snaps. What we’re really after is the distribution of how many Thanoses are poofed per snap (PPS for you sabermetricians).
As solver Tracy Hall explained, for the case of one Thanos, half of humanity survives. For two Thanoses, though, we don’t know whether the first snap takes out the second Thanos. Half the time, one Thanos survives, leaving 1/4 of humanity, and half the time, the second Thanos doesn’t survive, leaving 1/2 of humanity, for an overall average expected survival rate of 3/8. For three Thanoses, the probabilities are 1/4, 1/2 and 1/4, respectively, that zero, one or two Thanoses remain after the first snap, from which we can calculate the ensuing probabilities from a possible second snap, and a third snap, which at the end yields a more optimistic survival rate (19/64) than we would’ve gotten using the (wrong) methodology described above.
All this means that 1) this problem probably should have been a Riddler Express and a Riddler Classic and 2) the survival rates as a function of N can be calculated recursively using the binomial coefficients and the previously calculated values. (As I said, a Riddler Classic.)
The right answer, at the end of all this calculation (some of which I have chosen to spare you), is that about 166.5 million people are expected to survive — honestly not bad considering more than five dozen all-powerful beings out to destroy everyone.
Lastly, solver Laurent Lessard illustrated the survival rate as the number of initial Thanoses grew:
Be careful out there.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Dan Z. and the Nerd Herd ÑÑâÐ of Richmond, Virginia, winners of last week’s Riddler Classic!
Last week brought you a brand-new version of Riddler Nation’s favorite game show, Guess Your Hat. It was a colorful version, and it worked as follows: You and three friends each had a hat placed on your head, and it could be any one of four colors: red, yellow, blue or green. You could see everyone else’s hat but not your own, and your goal was to guess the color of your own hat. Guess right and you win; guess wrong and you lose. Guesses were made in private. You couldn’t communicate with your friends in any way during the game, but you could communicate with them beforehand to decide on a strategy. But the showrunners would be listening in, which means that they knew whatever strategy you decided on. And they then chose the hats in the worst possible way (for you), trying to make as many people as possible lose. Given the behavior of the nefarious showrunners, you probably couldn’t pick a strategy that would let everybody win. But could you design a strategy that guaranteed at least one of you would win?
You could indeed guarantee victory for one friend, but no more.
Here’s how to do that in just a few simple steps, adapted from the solution of solver Christopher Clark. The key is modulo arithmetic. First, assign numbers to the colors, for instance like so: red = 0, blue = 1, green = 2, yellow = 3. Therefore, using this approach, the four hats distributed in the game show will add up to something between 0 and 12. And, importantly, they will add up to something between 0 and 3, modulo 4 — that is, the remainder of their sum when divided by 4 will be between 0 and 3. (For example, 7 modulo 4 equals 3, because 4 goes into 7 once, leaving a remainder of 3. Another: 2 modulo 4 equals 2, because 4 goes into 2 zero times, leaving a remainder of 2.) Essentially, this arithmetic process shrinks the space of numbers from 0 to 12 into numbers from 0 to 3, which is great because we have four hats and four colors we need to deal with.
Assign the friends numbers, too — these will help determine what their guesses will be. For example, Friend 1 assumes the sum of all the hat colors is 0 (modulo 4), Friend 2 assumes it’s 1, Friend 3 assumes it’s 2 and Friend 4 assumes it’s 3. And then each friend should guess the color that would match their assumption. This guarantees that one friend will be correct, no matter what the devious showrunners do.
For example, suppose the devious showrunners outfit the friends as follows:
Friend 1: Blue hat
Friend 2: Blue hat
Friend 3: Red hat
Friend 4: Yellow hat
Friend 1 sees his friends’ hats as 1 + 0 + 3 = 4, which equals 0 (modulo 4). That matches his assumption about all of the hats’ total sum. He wants to keep that sum unchanged, so he picks red, which is worth 0, to keep the total at 4.
Friend 2 sees 1 + 0 + 3 = 4, so picks blue to make it 5
Friend 3 sees 1 + 1 + 3 = 5, so picks blue to make it 6
Friend 4 sees 1 + 1 + 0 = 2, so picks blue to make it 3
And Friend 2, who did indeed have a blue hat, wins.
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.