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.
Riddler Express
From Benni Trachtenberg, it’s time to dust off your football manager’s blazer just in time for the women’s World Cup:
A soccer coach is assembling a team of 11 players to compete in the Riddler League. (For the sake of this problem, all players are invincible and will play the entirety of every game of the season.) The coach may pick any player he wants from an infinite pool of players. It’s hard to remember that many names, so each player wears a jersey with a unique positive integer on the back (so that there is a player for every integer). That number also represents the average number of games needed for her to score a goal.
The coach would like his team to average exactly two goals per game but would also like for his weakest player to be as strong as possible. What number does the ideal weakest player wear? What are the numbers of the other 10 players the coach should select?
Riddler Classic
From Dean Ballard, one small step for man, one giant problem for The Riddler:
Sometime in the near future people from Earth will land on Mars. Someone will step out of the landing pod and become the first human to leave his or her footprints on another planet.
Imagine two astronauts sitting in the pod, both of whom would love to take that first step. But they would also like to decide which of them gets the honor in a fair manner, so they flip a coin. Despite the change in gravity, this method is fair as long as the coin is fair. If there were four astronauts in the landing pod, then they could flip a fair coin twice, assigning the four possible outcomes — heads-heads, heads-tails, tails-heads and tails-tails — to each of the four astronauts. This would also be fair as long as the coins were fair.
But what if there were three astronauts in the landing pod? Then our fair coin doesn’t work so well. We could, for example, assign three of the four possible outcomes — say heads-heads, heads-tails and tails-heads — to each of the astronauts. Then, if the outcome were tails-tails, they could simply start over again with two more flips. This would give an ever-increasing probability that a fair decision would eventually be made, but that could take a long time, and the required number of flips would be unknown. And there’s a planet to walk on!
Another approach, however, is to use an “unfair coin” — one in which the probabilities of heads and tails are not equal. Is it possible to make a fair choice among three astronauts with a fixed number of flips of an unfair coin?
You are able to set the coin’s probability of heads to any number you like between 0 and 1. You may flip the coin as many times as you like, as long as that is some known, fixed number. And, you may assign any combination of possible outcomes to each of the three astronauts.
Extra credit: What if there were five astronauts?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Mary Lo ÑÑâÐ of Alhambra, California, winner of last week’s Riddler Express!
Last week had you contemplating a color maze, shown below. You were meant to navigate it three times — once as blue, once as yellow and once as red. If you were blue, you were only allowed to travel on those colored paths that contained blue: blue, green, purple and white (which contains all colors). You were not allowed to travel on orange, yellow, red or black (which contains no colors). The analogous rules held for your journeys as yellow and red.
Some solvers — myself included — approached the problem armed with intuition and trial-and-error alone. You knew, for example, the white paths could be especially useful, since they are navigable no matter what color you are. And, indeed, the series of white paths at the top (for your journey as blue) and the series of white paths at the bottom (for your journey as yellow) were key.
Others, cleverer than I, used image processing software to isolate the navigable colors for each journey, therefore making the paths immediately visually obvious. Here, for example, are the valid paths for the blue journey, as created by solver Adam Diehl:
And finally, no matter how you got there, solver Vikrant Kulkarni provided the following illustration of the three successful paths from start to finish:
May your travels always be so colorful.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Daniel Mikkelson ÑÑâÐ of Cary, North Carolina, winner of last week’s Riddler Classic!
HBO’s “Game of Thrones” may have ended, but we can still contemplate its intricate mathematics. Last week, for example, brought us to a pivotal moment in an epic battle between the armies of the living and the dead. The Night King, head of the army of the dead, could raise all the fallen (formerly) living soldiers to join his ranks. That ability obviously presented a huge military advantage, but how huge exactly?
We simplified this battle and modeled it as follows: Each army lined up single file, facing the other army. One soldier stepped forward from each line and the pair dueled — half the time the living soldier won and half the time the dead soldier won. If the living soldier won, he went to the back of his army’s line, and the dead soldier was out (dead forever this time). If the dead soldier won, he went to the back of his army’s line, but in that case, the (formerly) living soldier joined him there. The battle continued until one army was entirely eliminated. The question: What starting sizes of the armies, living and dead, gave each army a 50-50 chance of winning?
If the army of the dead had \(N\) soldiers, the army of the living would need on the order \(N^2\) to have a fair fighting chance. So, for example, if the dead could muster even 100 fighters, the living would need a legion of 10,000 just to make it interesting. The relationship is exponential because the living army, if one of its soldiers dies, not only loses a troop of its own but also donates one to the opposition that can fight against it — therefore, the living need exponentially more troops with which to begin.
Dan Swenson, a math professor at Black Hills State University, shared a detailed write-up of his, well, mathematical approach. But most of you turned to your computers, simulating thousands of epic battles and millions of reanimations. For example, solver Matthew Johnston modeled the problem in R, and Matt Dutson did the same in Python.
As a result, these simulations also generated some lovely visualizations. Jason Ash gave us not only the army sizes for a 50-50 battle, but also for the chances that the living win 30, 40 and 60 percent of the time:
Laurent Lessard gave us another look at it, illustrating, in the white region, those army sizes for which the battle is more or less fair.
And finally, Flavio Lehner got colorful, illustrating how quickly the living army needs to grow to keep competitive pace with the dead, and how much trouble it’s in if it doesn’t.
Yea, though I walk through the valley of the shadow of death, I will fear no evil: for thou \(N^2\) other living soldiers art with me.
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.