How Much Money Can You Pull Out Of A Hat?
Illustration by Guillaume Kurkdjian
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the 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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.
Riddler Express
In advance of the 2013-14 season, the NBA changed the format of the NBA Finals, a best-of-seven series. Previously, the Finals used a “2-3-2” format: Games 1, 2, 6 and 7 were played in the home arena of the higher-seeded team, while Games 3, 4 and 5 were in the arena of the lower-seeded team. With the change, the Finals moved to the “2-2-1-1-1” format: Games 1, 2, 5 and 7 were at the home of the higher-seeded team, while games 3, 4 and 6 were at the home of the lower-seeded team.
Suppose you play for the higher-seeded team heading into the Finals. While your team had a better record during the regular season, the two teams are evenly matched — at a neutral site, both teams are equally likely to win a game. But of course, no game in the Finals is played at a neutral site. Both teams have a 60 percent chance of winning each home game and a 40 percent chance of winning each away game.
Which format — 2-3-2 or 2-2-1-1-1 — gives your team a better chance of winning the Finals? (Or are they the same?)
Extra credit: What are your team’s chances of winning the Finals under each format?
Riddler Classic
From Yonah Borns-Weil comes an opportunity to (probably) win a lot of money:
You start with just the number 1 written on a slip of paper in a hat. Initially, there are no other slips of paper in the hat. You will draw from the hat 100 times, and each time you draw, you have a choice: If the number on the slip of paper you draw is k, then you can either receive k dollars or add k higher numbers to the hat.
For example, if the hat were to contain slips with the numbers 1 through 6 and you drew a 4, you could either receive $4 or receive no money but add four more slips numbered 7, 8, 9 and 10 into the hat. In either case, the slip with the number 4 would then be returned to the hat.
If you play this game perfectly — that is, to maximize the total amount of money you’ll receive after all 100 rounds — how much money would you expect to receive on average?
Solution to the last Riddler Express
Congratulations to 👏 Izumihara Ryoma 👏 of Toyooka, Japan, winner of last week’s Riddler Express.
Last week’s puzzle was inspired by the game Digit Party, in which you place 25 digits one at a time on a five-by-five board. Whenever two of the same digits are placed in adjacent squares (whether horizontally, vertically or diagonally adjacent), you get a number of points equal to the value of those two digits.
For example, if you place four 1s in a row, you get 3 points, as there are three adjacencies. If you instead place those 1s in a two-by-two square, you get 6 points, as there are now six adjacencies (including the two diagonals).
For last week’s puzzle, you had to place 16 1s on an infinite grid that was initially empty. What was the maximum number of points you could earn?
To maximize the number of connections between the 1s, you wanted an overall compact geometry. Many solvers started with a four-by-four square, which was certainly worth quite a few points:
Just how many points was this arrangement worth? There were 12 horizontal connections, 12 vertical connections and nine pairs of diagonal connections. In total, the four-by-four square was worth 42 points.
But it was possible to do even better! Instead of the square formation, consider the arrangement below:
This time around, there were 12 horizontal connections, 11 vertical connections, eight pairs of diagonal connections and four additional diagonal connections around the perimeter. In total, this arrangement was worth 43 points, one more than the square, and was therefore the solution to this week’s puzzle.
For extra credit, the number of 1s you had to arrange increased from 16 to 100 and 1,000. The puzzle’s submitter (and one of the creators of Digit Party), Vince Vatter, shared a recent article that explored this problem in greater detail. It turns out that the maximum number of connections given N 1s tracks very closely to Nlog(N) for a while, which you can see for yourself via the corresponding OEIS sequence. (Of course, this pattern can’t last forever, since the additional number of connections you get by adding another 1 is surely bounded.)
The article goes on to conjecture that the optimal arrangement can be produced via an “octagon spiral,” as illustrated below.
The article further states that the number of connections in an octagon spiral with N 1s is 4N−⌈√(28N−12)⌉. When N was 100, this expression was 347 and when N was 1,000, this expression was 3,832.
Solution to the last Riddler Classic
Congratulations to 👏Alexander Bolton 👏 of London, United Kingdom, winner of last week’s Riddler Classic.
Last week, aliens were visiting Earth to announce their intent to blow up the planet. (Lovely.)
However, they presented you with a challenge. If you successfully completed the challenge, they’d blow up another planet instead. (Probably Neptune, because why not.)
The aliens had telepathically assigned each of the 8 billion human beings on Earth a unique random number, uniformly distributed between 0 and 1. Each human being knew their own number, but no one else’s. Your challenge was to identify the person with the highest number.
The aliens allowed you to ask a single yes-or-no question to all 8 billion people. This question had to be the same for everyone and would be answered simultaneously by everyone. The aliens had courteously agreed to aggregate the data for you as to who answered your question yes or no.
What question would you have asked, and what were your chances of saving the world?
As with a previous Riddler Classic, your strategy was to ask all 8 billion people whether their number exceeded a certain threshold value, t. Then, among the folks who answered in the affirmative, you’d pick a random person and hope that they were the one with the highest number.
From there, all you had to do was figure out which value of t maximized your chances of saving the world. And to do that, you had to find an expression for this probability in terms of t.
The probability that a randomly selected person’s number was less than or equal to2 t was, well, t. And the probability their number was greater than t was 1−t. So the probability that everyone’s number was less than t was t8,000,000,000. The probability that exactly one person had a number greater than t (an ideal scenario that guaranteed you’d save the world!) was (8,000,000,000)·(1−t)·t7,999,999,999. In this expression, the coefficient of 8 billion was due to the fact that any of the 8 billion people in the world could have been the one with the number greater than t.
The probability that exactly two people had a number greater than t was 8 billion choose 2, or (8,000,000,000)·(7,999,999,999)/2, times (1−t)2·t7,999,999,998. But that wasn’t your probability of saving the world in this scenario. Among the two people whose numbers exceeded t, you had to guess which one had the greater value, which you had a 50 percent chance of doing correctly. So the probability that exactly two people had a number greater than t and you saved the world was (8,000,000,000)·(7,999,999,999)/2·(1−t)2·t7,999,999,998/3. In general, the probability that exactly N (greater than zero) people had a number greater than t and you saved the world was 8 billion choose N times (1−t)N·t8,000,000,000−N/N.
At this point, you had to add these expressions for all values of N between 1 and 8 billion, although for values of t close to 1 many of these expressions with larger values of N were negligible. Some solvers did this by summing most or all of these 8 billion terms using a computer, while others, like Josh Silverman, used approximations that worked well for large populations like 8 billion. In the end, the probability of saving the world was maximized when t was approximately 1−1.88×10-10. And so, the question you would have asked everyone was, “Is your number greater than 1−1.88×10-10?”
The probability of saving the world was very sensitive to this value of t, as Josh demonstrated with the figure shown below. Interestingly, your chances of saving the world were greater than 50 percent! With the optimal value of t, this probability turned out to be about 51.7 percent — just a little better than the flip of a coin. So — are you feeling lucky?
Want more puzzles?
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 Zach Wissner-Gross at riddlercolumn@gmail.com.
