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 Dean Arvidson, I’ll take a math problem for $200, Alex:
Austin Rodgers is having quite a run on the game show “Jeopardy!” As The Riddler goes to press, he’s won $411,000 over 12 days. What’s the maximum amount of money that can possibly be won by one contestant in a single game of “Jeopardy!”?
Riddler Classic
From Guy Moore, a miniature version of “football” you can play on the couch while still eating nachos:
Coinball is a contest where two players take turns trying to call a fair coin toss. The game lasts for 100 total tosses, 50 tosses for each player. On each toss, the player calling it announces either “heads” or “tails” and either “rush” or “pass.” If he says “rush,” he gets one point if he calls the toss correctly, and his opponent gets one point if the call is incorrect. Saying “pass” means the toss is worth two points to the caller if he calls the toss correctly and two points to his opponent if he does not. At the end, the player with the most points wins. (The margin of victory is irrelevant; in Coinball, league rankings are based only on wins, with a draw counting as half a win.)
- If you know your opponent always calls “rush” and you follow the optimal strategy given that knowledge, what are your chances of winning?
- What if you know your opponent always calls “pass”?
- If you and your opponent both play optimally, is it better to go first? Or to go second and therefore get the last call?
Extra credit: Put your Monte-Carlo simulations away and try to determine the win probabilities to 10 digits of precision.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Joseph Wetherell ÑÑâÐ of San Diego, winner of last week’s Express puzzle!
A farmer has three daughters. He is getting old and decides to split his 1-mile-by-1-mile farm equally among his daughters using fencing. What is the shortest length of fence he needs to divide his square farm into three sections of equal area?
As you begin to plan your fence-building, you might sketch out a few blueprints and measure how much fence you’d need.
You start off simple, just planning to build two plain old east-to-west fences across the farm. These divide your farm into three identically shaped horizontal slices, giving you the equal areas you desire. This first arrangement uses 2 miles of fence.
But nothing is forcing you to go east to west. So you draw a blueprint where a vertical fence line meets a horizontal fence line, as shown in the second diagram. Again, you’ve divided your farm into three regions of equal area, although this time not identically shaped. This arrangement uses 1+2/3 or about 1.67 miles of fence. Much better! If you made it this far, you are a conscientious and efficient farmer and have done the agricultural sector of Riddler Nation proud.
But then you have an epiphany: There’s no reason the fences need to be east-west or north-south at all — they could be diagonal! So you sketch out a blueprint like the third diagram, where fences meet in a Y shape to split up the farm. But now things get a little more complicated because you need to figure out where exactly to put the diagonal lines and how much fence this’ll take. You’ll need a little algebra and a touch of calculus. First you figure out what the distances \(x\) and \(y\) must be.2 You know each region must have an area of 1/3, so you know, using the formulas for the area of a rectangle (base times height) and a triangle (one-half base times height), that \(y/2 + x/4 = \) 1/3. In other words, \(y = 2/3 – x/2\).
So how much fence does this arrangement use? It uses one vertical piece (length \(2/3 – x/2\)) and two diagonal pieces. The diagonal pieces are the hypotenuses of right triangles, so we can get their length from the Pythagorean theorem: \(x^2 + (1/2)^2 =\) that length of fence squared. Then we take the square root of that (which is the length of one diagonal) and add two of them to \(y\), which gets us the total length of fence in this arrangement. (Call it \(L\).)
\begin{equation*}L = (2/3 – x/2) + 2\sqrt{x^2 + 1/4}\end{equation*}
Your job as super-efficient farmer is to select the x that minimizes that total length \(L\). You can do this by taking the derivative of \(L\) with respect to \(x\) and setting it equal to zero. That gives \(x = 1/(2\sqrt{15})\). Plugging that back into our equation for \(L\), this arrangement uses about 1.635 miles of fence. Even better than our second fence! If you made it this far, you earned a blue ribbon in the Riddler Nation agricultural expo.
But then you have another epiphany and nearly pass out: There’s no reason the fences need to be straight — they could be curved! So you sketch a blueprint like the fourth diagram. It’s similar to the third, except the “arms” of your fence arrangement are bits of larger circles.
The math here gets more complicated still. But in the end it turns out that \(z\), the “stem” of your fence arrangement, is about 0.576 miles long, the circle itself has radius one, the angle pictured3 is 30 degrees, and the entire thing takes about 1.623 miles of fence. Our best result yet! If you made it this far, congratulations: You’re Riddler Nation’s new minister of agriculture.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Joseph Lombardo ÑÑâÐ of Chicago, winner of last week’s Classic puzzle!
Last week, you and three of your friends went on a game show. On stage was a sealed room, and in that room were four sealed, numbered boxes. Each box contained one of your names, and each name was in one box. You and your friends took turns entering the room alone and opening up to two boxes, with the aim of finding the box containing your name. By rule, everyone enters exactly once. Your team could confer on a strategy before stepping on stage, but no communication was allowed during the show — no player knew the outcome of another player’s trip into the room. Your team won if everyone found the box containing his or her name and lost if any player failed to do so. If each person opens two boxes at random, the chance of winning is only 1/16. Call this the naive strategy. Your goal was to concoct a strategy that beats the naive strategy — one that gives the team a better chance of winning than 1/16.
There is a strategy that gives a probability of winning of 10 in 24, or a bit under 42 percent. It works like this, adapted from the puzzle’s submitter, Jared Bronski:
Your team begins by agreeing on a number for each player, for example, Isabel = 1, John = 2, Kevin = 3 and Lillian = 4. Each player begins by opening the box that’s labeled with his or her number. Isabel opens Box 1, John opens Box 2, and so on. If they find their own name, they’re done. If not, they take the name they do find in the box as an instruction and open the box corresponding to that name’s number. For instance, Isabel will first open Box 1. If she finds Lillian’s name inside, she will then open Box 4.
The names and boxes together form a permutation. Every permutation can be expressed as the result of cycles. For example, the permutation (1,4)(2,3) is made up of two cycles. The first means Box 1 leads to Box 4 and Box 4 leads to Box 1. (That loop is what makes it a cycle.) The second cycle shows that Box 2 goes to Box 3 and Box 3 goes to Box 2. On the game show, this would correspond to Box 1 containing Lillian’s name, Box 2 containing Kevin’s, Box 3 containing John’s and Box 4 containing Isabel’s. If, as in this case, all of the cycles have a length of two or less, then the team will win — all players will find their own names after one or two boxes.
If a cycle has a length of three or four, the players will lose because they can only open up to two boxes. For example, the permutation (1,2,3)(4) would correspond to Box 1 having John’s name, Box 2 having Kevin’s, Box 3 having Isabel’s and Box 4 having Lillian’s. In this case, Lillian would find her own name, but Isabel, John and Kevin would not.
There are four names and four boxes, so there are a total of 4×3×2×1 = 24 permutations, 14 of which are too long to lead the team to victory.
To learn that 14 cycles are too long to work, we simply figure out how many cycles have a length of three or four. Six permutations contain a cycle of length four. It’s easy to see why: In these scenarios, Box 1 can contain three names — 2, 3 or 4. (It can’t contain Name 1 or that cycle would be over.) For the sake of argument, let’s say it contains Name 4. Then Box 4 can contain either 2 or 3. So there are 3×2 = 6 permutation possibilities.
Eight permutations contain a cycle of length three. Importantly, that also means that one of the cycles will have a length of one — in other words, that box will have the name that corresponds to the number it was assigned. There are four ways that one of the boxes could contain its corresponding name. The other three boxes must form a cycle of length three, and there are only two ways to do this, since none of these other three boxes can have their corresponding names inside. Multiply those possible combinations and you get 4×2=8. Add that to the number of four-cycle permutations above, and you get 6+8 = 14 permutations in which the players lose. That leaves 10 left over in which the players win.
For extra credit, you were asked how well you could do if there were 100 people and 100 boxes instead of four, and each player could each open up to 50 boxes instead of two. The same basic strategy applies. Associate a number with each name. Open your own box, then follow the trail, opening the box pointed to by the name in your current box. Continue until you have either opened 50 boxes or found your name.
As before, the boxes contain a permutation of the names. You will win if the cycles making up this permutation have length 50 or less and lose if there is a cycle with a length of more than 50. The probability of having a cycle of length at least 50 is (after some combinatorics)
\begin{equation*}1/51 + 1/52 + 1/53 + \ldots + 1/100 = 0.6882\end{equation*}
So the chance of winning is 1-0.6882 = 0.3118, or a bit over 31 percent. This is markedly better than your chances when each player guesses randomly — those are about 1 in \(10^{30}\).
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.