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,9 and you may get a shoutout in next week’s column. If you need a hint, or if you have a favorite puzzle collecting dust in your attic, find me on Twitter.
From Ted Vician, an Oval Office stumper:
Let’s say you’re the president of the United States. You have a problem: Someone on your staff keeps leaking stories to the press. So you and your new chief of staff devise a plan. You will give different pieces of information to different staffers so that you’ll learn who the leakers are by what information ends up in the newspaper or on TV. (You know you have only one leaker, and you know he or she leaks any story he or she is given.)
If there are 100 people on your staff, how many different stories do you need to identify your leaker for sure?
From Dan Waterbury, a tricky table-top geometry problem:
Fans of Dungeons & Dragons will have fond feelings for four-sided dice, which are shaped like regular tetrahedrons. Some might have noticed, in those long hours of fantasy battle, that if you touch five of these pyramids face-to-face-to-face, they come agonizingly close to forming a closed pentagon. Alas, there remains a tiny angle of empty space left between two of the pyramids.
What is the measure of that angle?
Solution to last week’s Riddler Express
Congratulations to Jillian Waid of Orwell, Ohio, winner of last week’s Express puzzle!
A class of 30 children is playing a game where they all stand in a circle along with their teacher. The teacher is holding two things: a coin and a potato. The game progresses like this: The teacher tosses the coin. Whoever holds the potato passes it to the left if the coin comes up heads and to the right if the coin comes up tails. The game ends when every child except one has held the potato, and the one who hasn’t is declared the winner. How do a child’s chances of winning change depending on where they are in the circle? In other words, what is each child’s win probability?
Surprisingly (to me, anyway) each child, no matter where they are in the circle, has the same win probability: 1/30!
The puzzle’s submitter, Chris Thornett, walks us through how to get there:
Let’s choose a random child and call her Carol. Call the people to her left and right Angela and Bob, respectively. (Angela or Bob could be the teacher.) Either Angela or Bob (or both) must touch the potato before Carol. If Angela touches the potato before Bob, then Carol will win if — and only if — Bob touches it before she does, because this will involve the potato being passed via every other child.
The probability of this happening is the same as the probability of a simple random walk moving 29 places to the left before it moves one place to the right. That probability can be calculated as one in 30 (using techniques such as the optional stopping theorem from martingale analysis). Of course, if Bob touches the potato before Angela, then Carol’s win probability is exactly the same, by symmetry. We are now looking instead at a random walk moving 29 places to the right before it moves one place to the left, but the probability does not change. So the probability given either scenario (which are mutually exclusive, and one must happen) is one in 30, so the overall probability is one in 30.
Solver Jason Ash confirmed this mathematical result with 2 million computer simulations of this game of hot potato:
Solution to last week’s Riddler Classic
Congratulations to Alexander Kobulnicky of Portland, Maine, winner of last week’s Classic puzzle!
There is a bathroom in your office building that has only one toilet. There is a small sign stuck to the outside of the door that you can slide from “Vacant” to “Occupied” so that no one else will try the door handle (theoretically) when you are inside. Unfortunately, people often forget to slide the sign to “Occupied” when entering, and they often forget to slide it to “Vacant” when exiting. Assume that 1/3 of bathroom users don’t notice the sign upon entering or exiting. Whatever the sign reads before their visit, it still reads the same thing during and after their visit. Another 1/3 of the users notice the sign upon entering and make sure that it says “Occupied” as they enter. However, they forget to slide it to “Vacant” when they exit. The remaining 1/3 of the users are very conscientious: They make sure the sign reads “Occupied” when they enter and “Vacant” when they exit. Finally, assume that the bathroom is occupied exactly half of the time.
There is a 62.5 percent chance that the bathroom is occupied if the sign says “Occupied.” There is a 75 percent chance that the bathroom is vacant if the sign says “Vacant.”
The puzzle’s submitter, Dave Moran, explains the math:
Call the three types of users conscientious (C), semi-conscientious (S) and unconscientious (U). C makes sure the sign is “Occupied” upon entering and “Vacant” upon exiting. S makes sure the sign is “Occupied” upon entering but leaves it at “Occupied” upon exiting. U doesn’t notice the sign at all.
If the sign reads “Occupied,” there are four possibilities:
- Bathroom is occupied by a C.
- Bathroom is occupied by an S.
- Bathroom is occupied by a U, and the most recent previous user who was not a U was an S.
- Bathroom is vacant, and the most recent previous user who was not a U was an S.
Possibilities 3 and 4 require a bit of explanation. If the bathroom is currently occupied by a U, it doesn’t matter how many of the preceding users were also U. All that matters is whether the most recent non-U was an S or a C. If it was a C, the sign would read “Vacant” — that conscientious user would’ve slid the sign to “Vacant” upon exiting, and the unconscientious users wouldn’t have changed it. If it was an S, it would read “Occupied.” The same reasoning applies to 4 if the bathroom is currently vacant.
So, the probability that the bathroom really is occupied is simply: [(1) + (2) + (3)]/[(1) + (2) + (3) + (4)]
The probability of (1) = 1/2 x 1/3 = 1/6 (1/2 chance the bathroom is really occupied and 1/3 chance it’s a C)
The probability of (2) = 1/2 x 1/3 = 1/6 (1/2 chance the bathroom is occupied and 1/3 chance it’s an S)
The probability of (3) = 1/2 x 1/3 x 1/2 = 1/12 (1/2 chance the bathroom is occupied, 1/3 chance it’s a U and 1/2 chance most recent user who was not a U was an S)
The probability of (4) = 1/2 x 1/2 = 1/4 (1/2 chance the bathroom is vacant, 1/2 chance most recent user who was not a U was an S)
So the probability is [5/12]/[2/3] = 5/8 = 62.5 percent chance the bathroom is occupied if the sign says “Occupied.”
If the sign reads “Vacant,” there are only two possibilities:
- Bathroom is vacant, and the most recent previous user who was not a U was a C (because an S would have left the sign at “Occupied”).
- Bathroom is occupied by a U, and the most recent previous user who was not a U was a C.
The probability of (5) = 1/2 x 1/2 = 1/4
The probability of (6) = 1/2 x 1/3 x 1/2 = 1/12
(5)/[(5) + (6)] = [1/4]/[1/3] = 3/4 = 75 percent chance the bathroom is vacant if the sign says “Vacant.”
For the more visual among you, solver Billy Hines illustrated the possibilities of trips into and out of the bathroom and what that means for the state of the sign:
For extra credit, solver Matt Fay illustrated how these probabilities change as the types of bathroom users in your office change. Intuitively, the more conscientious the employees are, the more accurate the bathroom sign becomes:
Want to submit a riddle?
Email me at email@example.com.