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.
This week, two two-dimensional geometrical mysteries …
Riddler Express
From Jim Nugent, a piece of a hexagon:
The regular hexagon below has an area of 1. What is the area of the shaded region?
Riddler Classic
From Tyler Barron, a snaking circle, via a problem-solving course at Boston University:
The largest circle below has a radius of 10, the medium circle has a radius of 5 and the small, orange circle has a radius of 2. The orange circle crawls counterclockwise along the edge of the largest circle until it meets the medium circle, at which point it crawls up along the edge of the medium circle until it reaches the crest. What is the area of the shaded orange region in the right image?
Solution to last week’s Riddler Express
Congratulations to 👏 Rich Frothingham 👏 of Durham, North Carolina, winner of last week’s Express puzzle!
Last week, you challenged your friend to a friendly game: You took turns taking matchsticks from the arrangement shown below. You alternated taking sticks, and the person who picked up the last stick lost. On your turn, you could pick up as many sticks from any single row as you wanted, but you had to pick up at least one stick. You went first.
|
| | |
| | | | |
| | | | | | |
If your opponent plays her matchsticks right, you will always lose. Here’s why:
As you and your friend play, picking up sticks on each turn, there are 383 different arrangements of sticks that could occur. (Each row can contain between zero and its initial number of sticks, and the board can’t have zero sticks. So the first row can have zero or one sticks (two possibilities), the second can have zero, one, two or three sticks (four possibilities) and so on, which gives us 2×4×6×8–1 = 383.) That’s not enormous, and we could go through and analyze each one by one. But we don’t really need to.
As solver Hans Zhou explained: There are 20 fail states. A fail state is a situation in which, if it’s your turn, you are going to lose eventually. If you find yourself in any one of these fail states, a perfect player can always stick you right back in another fail state, no matter what move you make. The starting state (one stick in the first row, three in the second, five in the third, seven at the bottom) is one. If you go first against a perfect player, resistance is futile.
Here are the fail states, written as lists of the number of matchsticks in remaining piles:
1 (game over)
1, 1, 1
2, 2
1, 1, 2, 2
3, 3
1, 2, 3
1, 1, 3, 3
4, 4
4, 5
1, 4, 5
1, 1, 4, 4
2, 4, 6
1, 1, 5, 5
1, 2, 5, 6
3, 4, 7
1, 2, 4, 7
1, 3, 4, 6
2, 5, 7
3, 5, 6
1, 3, 5, 7 (starting position)
Take (1, 1, 1) as an example. In that case, you have to take one stick, which leaves (1, 1), in which case your friend takes one stick and you are left with the final stick — and you lose. If (2, 2) remains, you can either take one or two sticks from one of the piles. If you take two, your friend takes one and beats you. If you take one, your friend takes the other two and beats you. We can follow patterns like this all the way back to the beginning of the game. No matter what you do from the start, your opponent can play you into a corner.
Those who have a more formal background in math or computer science can best understand this game by thinking back to their binary lessons. A useful concept in this game (which is broadly called nim and has many variants) is called the nim-sum, which is often denoted by the symbol ⊕, rather than +. The nim-sum is a number that can help you find the optimal strategy in a given game and tell you, before the game starts, who is going to win. The nim-sum in this game is calculated by converting the number of sticks in each pile to binary and adding those numbers up, ignoring any carries from one digit to another. So 5⊕6, for example, equals 3 (5 is 101 in binary while 6 is 110 — adding those without carrying gives 011 in binary, or 3).2 A winning strategy is to end your turn on a nim-sum of zero, which you will always be able to do if the nim-sum at the start of your turn is not zero. In our game, the piles started with sized 1, 3, 5 and 7. In binary, that’s 001, 011, 101 and 111. Their nim-sum is zero, which means the first player will always lose.
This particular version of the game is known as Marienbad, after a scene in the 1961 French film “Last Year at Marienbad.” And indeed, the tuxedoed man in the movie who goes first loses to the tuxedoed man who goes second.
https://www.youtube.com/watch?v=bB3TTinXw4w
Solution to last week’s Riddler Classic
Congratulations to 👏 Jimmy Clowes 👏 of London, winner of last week’s Classic puzzle!
Last week, you met a frog that needed to jump across 20 lily pads. He started on the shore (No. 0) and ended precisely on the last lily pad (No. 20). He could jump one or two lily pads at a time. How many different ways could he reach his destination?
There are 10,946 different hopping paths that the frog could take.
There is only one way that the frog can “get to” No. 0: by sitting there. There is only one way the frog can get to No. 1: by jumping one pad. There are two ways it can get to No. 2: by leaping one pad twice or two pads once. There are three ways it can get to No. 3: by jumping one pad three times, jumping one and then two, or jumping two and then one.
More generally, the number of ways the frog can get to a given lily pad is the sum of the number of ways it can get to the two pads before it. Because the frog can jump one or two pads at a time, one of the two preceding pads is where it must have been before it got to its current pad. So it can get to its current pad however it got to the pad in front of it or however it got to the pad in front of that. Starting on the shore, the number of possible paths for further and further out pads: 1, 1, 2, 3, 5, 8, 13, …
These are the famous Fibonacci numbers! The 20th Fibonacci number (counting the initial “1” as the zeroth number) is 10,946 — our solution.
What if the frog could jump one, two or three pads at a time? The same sort of logic applies, except now the number of ways to get to a given lily pad is the sum of the number of ways it can get to the three pads before it: 1, 1, 2, 4, 7, 13, 24, … These are sometimes called the tribonacci numbers, and the 20th such number is 121,415.
If the frog can hop four pads at a time, we’re dealing with tetranacci numbers — 1, 1, 2, 4, 8, 15, 29, … — and the total possible paths is 283,953. Five pads and it’s pentanacci — 1, 1, 2, 4, 8, 16, 31, … — for a total of 400,096. And so on.
Solver Mike Seifert graphed the number of paths as the frog’s maximum jump gets longer and longer. The total number of paths increases quickly but settles down around 500,000. Being able to jump 20 pads at a time only adds one possible trip to your repertoire, after all.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.