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.
Riddler Express
From Michael Dell’Amico comes a riddle requiring some mental gymnastics:
After realizing that your friends on μετα (The Riddler Social Network) are more popular than you, you decide to make some new friends at your local gym, which is open daily from 5 p.m. to 8 p.m.
Some gym members attend very often. Others barely show up at all. As a matter of fact, there’s a uniform distribution for how often the different members are in the gym — from 0 percent of the time that the gym is open to 100 percent of the time.
As a new member, you plan to be in the gym 50 percent of the time that it’s open. While working out, you decide to make friends with the first person you see. (Aw!)
What is the probability that this person visits the gym more often than you?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
From Eric Dallal comes a variant of an oldie but a goodie — deducing the color of the hat on your head!
Four people are trying to escape from a room. Guards have placed a hat on each person’s head, and each hat is one of three colors: red, yellow or blue. The four people are arranged at the vertices of a square, with an obstacle in the middle. Each person can see the hats on the heads of those on adjacent vertices of the square, but they cannot see the hat of the person diagonally across from them. They also do not know the color of the hat on their own head.
Each person must guess the color of the hat on their own head. If at least one person guesses correctly, they can all escape the room together. No communication is allowed once the hats are placed on their heads, but they can coordinate on a strategy beforehand. They also know how they will be arranged in the circle.
How can they be guaranteed to escape the room?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Donald Adamek ÑÑâÐ of Canton, Michigan, winner of last week’s Riddler Express.
Last week, I had three dice (d4, d6, d8) on my desk that I fiddled with while working, much to the chagrin of my co-workers. For the uninitiated, the d4 is a tetrahedron that is equally likely to land on any of its four faces (numbered 1 through 4), the d6 is a cube that is equally likely to land on any of its six faces (numbered 1 through 6), and the d8 is an octahedron that is equally likely to land on any of its eight faces (numbered 1 through 8).
I was playing a game in which I rolled all three dice in “numerical” order: d4, then d6 and then d8. I won this game when the three rolls formed a strictly increasing sequence (such as 2-4-7, but not 2-4-4). What was my probability of winning?
There were four possible outcomes for the first roll, six outcomes for the second and eight for the third. All together, that meant there were 4·6·8, or 192, equally likely cases to consider. So then, for how many of these 192 cases did the rolls strictly increase?
Many solvers, like Angelos Tzelepis, figured this out by writing code to go through all the cases. Others, like Paige Kester (winner of last week’s Classic!), used a spreadsheet. In addition to these approaches, there were many ways to solve this by hand.
One such way was to first assume all three dice were d8s. Had that been the case, then each way of choosing three distinct values from 1 to 8 would have corresponded to a different possible sequence. And there were 8 choose 3 (or 56) ways to choose those three values.
But you didn’t really roll three d8s — you rolled a d4, a d6 and then a d8. So, out of those 56 sequences, four of them had an impossible first roll of 5 or 6: 5-6-7, 5-6-8, 5-7-8 and 6-7-8. And another four of them had an impossible second roll of 7: 1-7-8, 2-7-8, 3-7-8 and 4-7-8. Subtracting these eight impossible sequences left 48 that were indeed possible. The probability of such a sequence was therefore 48/192, or 1/4.
For extra credit, instead of three dice, I now had six dice: d4, d6, d8, d10, d12 and d20. If I rolled all six dice in “numerical” order, what was the probability I’d get a strictly increasing sequence?
This time around, there were 4·6·8·10·12·20, or 460,800, equally likely cases, which meant using a computer was definitely a good idea. Solver Chris Sears tallied up the number of strictly increasing sequences on a calculator:
Of the 460,800 cases, 5,434 were strictly increasing. That meant the probability was 5,434/460,800, or 2,717/230,400 — just a shade over 1 percent.
This was a little surprising (to me at least). Since I was rolling dice with larger and larger possible values, it felt like the probability of an increasing sequence should have been more likely.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Paige Kester ÑÑâÐ of Southlake, Texas, winner of last week’s Riddler Classic.
Last week, you played a game against a magic genie. You had a stick of length 1, while the genie had another stick behind his back, with a random length between 0 and 1 (chosen uniformly over that interval).
Next, you had to break your stick into two pieces and present one of those pieces to the genie. If that piece was longer than the genie’s hidden stick, then you won a prize of $1 million times the length of your remaining piece. For example, if you presented to the genie a length of 0.4, and that was longer than the genie’s stick, then you would win $1 million times 0.6, or $600,000. However, if the genie’s stick was longer, then you won nothing.
But then you had a thought. You asked the genie if you could have more than one turn. For example, if you presented the genie with a length of 0.4, but the genie’s stick was longer, could you break off a piece of the remaining length of 0.6 — say, a length of 0.5 — and then present that to the genie? To keep things fair, your winnings would still be proportional to the leftover length. So had the genie’s length indeed been between 0.4 and 0.5, your first and second guesses, then the remaining length would have been 0.1, and you would have won $100,000.
The genie didn’t think any of this really mattered and said you could have as many turns as you desired. If your goal was to maximize your expected winnings, what would have been your strategy? And how much money would you win on average?
First off, if you only had one chance to present a length to the genie, why would you have broken the stick in half? (Clearly, you knew something.) Suppose you presented a length A to the genie. The probability that it was greater than the genie’s random stick was also A, and your winnings were proportional to the remaining length, 1−A. That meant your average winnings were proportional to A·(1−A), a quadratic expression whose maximum occurred when A was 0.5. In other words, your best move was indeed to split the stick in half! Your average winnings were then $250,000.
Now, what if you had two opportunities to present lengths to the genie? Suppose your first length was A and your second length was B. For this to work, B had to be greater than A — otherwise, you were just being masochistic. Again, your expected winnings from the first length were A·(1−A). Meanwhile, the second length would win only when the genie’s length was between A and B, which occurred with probability B−A. And your winnings were proportional to 1−A−B, since that was all you had left after the two opportunities.
Putting all this together, your average winnings were proportional to the expression A·(1−A) + (B−A)·(1−A−B). Multiplying this out, you get A − A2 + B − AB − B2 − A + A2 + AB. Amazingly, almost all of the terms cancel, leaving you with just B−B2, or B·(1−B). This was the very same quadratic expression from before, now with B instead of A. So with two opportunities, you could first present any length between 0 and 0.5 (not including those two extremes). It really didn’t matter what the first length was. Then, if you lost, the second length should have been 0.5. Again, your expected winnings were $250,000.
Many solvers, including Emily Boyajian and Arvind Hariharan, went on to demonstrate that with three or more presentations to the genie, your expected winnings always maxed out at $250,000. When all was said and done, you couldn’t really stick it to the genie, and you might as well have presented a length of 0.5 on your first try.
I will also note that Riddler Nation proposed several interesting extension ideas for this puzzle. What if you could glue the presented pieces back together? What if the genie had a new random stick length every time you broke off a piece of your own stick? Sounds like the makings of a future riddle in which you’d get another shot at sticking it to that genie.
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 Zach Wissner-Gross at riddlercolumn@gmail.com.