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 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 Stephanie Thompson comes a question of ballot optimization:
Derek Jeter and Larry Walker were just elected to the Baseball Hall of Fame! That got Stephanie thinking. Suppose there are 20 players on the ballot and 400 voters in a given year. Each voter can select up to 10 players for induction without voting for any given player more than once. To gain entry, a player must have been selected on at least 75 percent of the ballots.
Under these circumstances, what is the maximum number of players that can be inducted into the Hall of Fame?
Riddler Classic
From Dean Ballard comes another coin-related challenge — a game of “Pinching Pennies”:
The game starts with somewhere between 20 and 30 pennies, which I then divide into two piles any way I like. Then we alternate taking turns, with you first, until someone wins the game. For each turn, a player may take any number of pennies he or she likes from either pile, or instead take the same number of pennies from both piles. Each player must also take at least one penny every turn. The winner of the game is the one who takes the last penny.
If we both play optimally, what starting numbers of pennies (again, between 20 and 30) guarantee that you can win the game?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Kealan Vasquez ÑÑâÐ of Ave Maria, Florida, winner of last week’s recent Riddler Express.
Last week, you were a coach in the Riddler Football League, and you had devised a new strategy for scoring after a touchdown. Your team would line up 2 yards away from the goal line in such a way that it could attempt either a 1-point conversion or a 2-point conversion. Your opponent could only properly defend against one of those two possibilities, so they’d have to guess.
If you attempted a 1-point conversion that was properly defended, you’d score 90 percent of the time; otherwise, you’d score 100 percent of the time. If you instead attempted a 2-point conversion that was properly defended, you’d score 40 percent of the time; otherwise, you’d score 60 percent of the time.
It was up to you to communicate to your team’s captain the probability with which they should attempt each. However, given all the spying that occurs in the League these days, you could assume that your message was overheard by your opponent, who also knew the probability of you scoring in each of the four scenarios listed above.
With all that said, what were the best offensive and defensive strategies here, and how many points would you score, on average, after each touchdown?
This was an example of a zero-sum game, meaning points were just as good for you as they were bad for your opponent. Since you and your opponent both had complete information about the probabilities, you’d pursue strategies that would result in a Nash equilibrium — that is, an effective stalemate where neither you nor your opponent would benefit from switching strategies.
Solver Ravi Chandrasekaran explored what would happen if you and your opponent tried different probabilities between always going for (or defending) 1 point vs. 2 points. Both Ravi and Kealan found that your best strategy was to go for 1 point 80 percent of the time and go for 2 points 20 percent of the time. To see why that is, suppose your opponent defends against 1 point with probability p and against 2 points with probability 1−p. How many points would you score on average? Let’s look at the four possible cases:
- You’d go for 1, and they’d defend it with probability 0.8p, earning 0.9 points on average (90 percent of 1 point).
- You’d go for 1, and they wouldn’t defend it with probability 0.8(1−p), earning 1 point on average (100 percent of 1 point).
- You’d go for 2, and they’d defend it with probability 0.2(1−p), earning 0.8 points on average (40 percent of 2 points).
- You’d go for 2, and they wouldn’t defend it with probability 0.2p, earning 1.2 points on average (60 percent of 2 points).
Combining all these cases, the average number of points you’d get will be 0.8p · 0.9 + 0.8(1−p) · 1 + 0.2(1−p) · 0.8 + 0.2p · 1.2 = 0.96 points. Notice how all the p’s cancel out? That means when you go for 1 point 80 percent of the time, it doesn’t matter what your opponent does — you’ll score an average of 0.96 points after each touchdown. If you were to veer away from these probabilities (say, by going for 2 more often), your opponent could take advantage (by defending against the 2 more often) and lower your average number of points.
Similarly, on the defensive end, when your opponent defends against 1 point 40 percent of the time and against 2 points 60 percent of the time, you’ll again score an average of 0.96 points, no matter what your offensive strategy is. At the end of the day, you could expect to score 0.96 points after each touchdown.
I am pleased to note that the many game theorists of Riddler Nation pointed out that, due to the defense overhearing what the offensive strategy was going to be (which was to go for 1 point 80 percent of the time), it technically didn’t matter what the defensive strategy was. It’s a great point! (Or was it a great 2 points?)
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Adam Richardson ÑÑâÐ of Old Hickory, Tennessee, winner of the last week’s Riddler Classic.
Last week, two delirious ducks were having a difficult time finding each other in their pond, which contained a 3×3 grid of rocks.
Every minute, each duck randomly swam from one rock to a neighboring rock in the grid — up, down, left or right but not diagonally. So if a duck was at the middle rock, it would next swim to one of the four side rocks with probability 1/4. From a side rock, it would swim to one of the two adjacent corner rocks or back to the middle rock, each with probability 1/3. And from a corner rock, it would swim to one of the two adjacent side rocks with probability 1/2.
If the ducks both started at the middle rock, then on average, how long would it take until they’re at the same rock again?
If the ducks were to make the same first move, they would have found each other after one minute. On the other hand, they could have gone around the rocks countless times without ever finding each other. A key insight was to realize that if you knew where the ducks were at some time, you could find a precise probability distribution for where they’d be one minute later. And because of the symmetry of the rocks, solver Jason Ash noted there were only five possible arrangements you had to keep track of:
For example, suppose after some time the ducks happen to be in the “outer across” arrangement in the above diagram. One minute later, there’s a 1/4 chance they’ll meet (if the left duck moves right and the right duck moves left), there’s a 1/4 chance they’ll switch to the “middle across” arrangement (if both ducks move down) and a 1/2 chance they’ll switch to the “diagonal outer” arrangement (if one duck moves down and the other moves horizontally).
By determining how likely the ducks transitioned between each of these different arrangements, solver Vikrant Kulkarni set up a system of equations relating the average times it took the ducks to meet from each arrangement, including the initial arrangement where both ducks were at the middle rock.
For problems like this, with random transitions between a fixed number of arrangements, many solvers, including Adam and Jason, used a technique knowns as Markov chains, which solve the very same equations Vikrant came up with. On average, the ducks will meet after 363/74, or about 4.905, minutes.
Solver Angelos Tzelepis went one step further, finding (after 3 million simulations) the probabilities of where the ducks would ultimately find each other. The most likely meeting point was where they started — the rock in the middle:
Despite his mathematical prowess, Angelos did make one critical error: He incorrectly referred to the ducks as “drunk.” They were merely delirious.
For extra credit, you were asked to consider the case of three or more ducks: If they all started in the middle rock, on average, how long would it take until they were all at the same rock again?
Again using Markov chains, solver Laurent Lessard was able to find exact values for the cases of three, four, five and six ducks, which would respectively take on average 18.4, 66.7, 237.4 and 825.3 minutes to all meet up. As the number of ducks increased, the time it took for them to meet appeared to grow exponentially, and the computation required to find the exact result became increasingly difficult.
To find approximate solutions for the general case where there were N ducks, solvers Guy D. Moore and Hector Pefo used the fact that after an odd number of minutes the ducks would all be on one of the four sides, and after an even number of minutes the ducks would all be in the middle or one of the four corners.
After an odd number of minutes — when the ducks were on the sides — no side was more likely to be where they met than any of the others. That meant the probability the ducks were all together at any given minute was 1/4N−1, where the minus one in the exponent came from the fact that the first duck could have been on any of the four sides, while the other N−1 ducks had to be on that same side. By performing a similar analysis after an even number of minutes, Guy and Hector found that N ducks would all meet up after approximately 2·3N minutes.
That meant it would take a dozen delirious ducks approximately two years to find each other. Meanwhile, it would take a dozen dozen delirious ducks far longer than the age of the universe to find each other.
Those poor dozen dozen ducks.
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.