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.
Quick announcement: Have you enjoyed the puzzles in this column? If so, I’m pleased to tell you that we’ve collected many of the best, along with some that have never been seen before, in a real live book! It’s called “The Riddler,” and it will be released in October — just in time for loads of great holidays. It’s a physical testament to the mathematical collaboration that you, Riddler Nation, have helped build here, which in my estimation is the best of its kind. So I hope you’ll check out the book, devour the puzzles anew, and keep adding to our nation by sharing the book with loved ones.
And now, to this week’s puzzles!
Riddler Express
From Freddie Simmons, a guessing game:
Take a standard deck of cards, and pull out the numbered cards from one suit (the cards 2 through 10). Shuffle them, and then lay them face down in a row. Flip over the first card. Now guess whether the next card in the row is bigger or smaller. If you’re right, keep going.
If you play this game optimally, what’s the probability that you can get to the end without making any mistakes?
Extra credit: What if there were more cards — 2 through 20, or 2 through 100? How do your chances of getting to the end change?
Riddler Classic
From Steven Pratt, use your econ, win some cash:
Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed $1 on the 1, $2 on the 2, $3 on the 3 and so on to $10 on the 10.
Each player has a personalized token. They take turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.
How will this game play out? How much is it worth to go first?
A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of $1 to $12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Jonathan Hegarty ÑÑâÐ of Cedar Grove, New Jersey, winner of last week’s Riddler Express!
Where on Earth can you travel 1 mile south, then 1 mile east, then 1 mile north, and arrive back at your original location?
You can do this at the North Pole, for starters — that’s the easy one. But there is also an infinite number of other such points on the planet that allow for this paradoxical navigation. Specifically, any point that is 1+1/(2nπ) miles from the South Pole, where n = 1, 2, 3, …
Our winner, Jonathan, explained how this works. At the North Pole, after walking a mile south (which could be any direction, since you’re as far north as possible) and a mile east, you would still be exactly 1 mile south of where you started. Therefore, when you walk north, you end up at your original position.
However, you can also do something similar if you are near the South Pole. We’re looking for a place that, after walking our first mile south, leaves us in position to walk 1 mile east and have that mile be a perfect circle around the South Pole. In other words we’re looking to start in a place that makes the circumference of the circle around the South Pole 1 mile, making the radius of that circle (and the distance to the South Pole) 1/2π. Once completing this circle, you are free to walk back north 1 mile to your starting point, which would be 1+1/2π miles in any direction from the South Pole. But you’re not limited to just taking a single circle around the South Pole. What if you want to walk a half-mile circle around the South Pole twice? In that case, you would want the radius of that circle to be 1/4π, so you would be starting 1+1/4π miles from the South Pole. Continuing that logic, you can really start at any place that is 1+1/(2nπ) miles from the South Pole, where n is any positive integer and the number of times you wish to walk around the South Pole.
Brrr.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Marissa James ÑÑâÐ of Berkeley, California, winner of last week’s Riddler Classic!
Last week found us in the factory of Riddler Rugs, where 100-by-100-inch random rugs are crafted by sewing together a bunch of 1-inch squares. Each square is one of three colors and is chosen for the final rug randomly. Riddler Rugs also wants its rugs to look random, so it rejects any finished rug that has a four-by-four block of squares of the same color. What percentage of rugs should we expect to be Riddler Rugs rejects? (Say that 10 times fast.)
Riddler Rugs will reject about 0.066 percent of its rugs, or roughly 1 rug in every 1,500.
We can arrive at that number in two different ways: a simple approximation and then a somewhat more involved one. My editor could barely stomach the former, let alone the latter, so tread carefully.
Let’s start with the approximation. Consider the fact that each of the squares in the top 97 “rows” and the left-most 97 “columns” of the quilt define an upper left corner of a four-by-four block. The squares are almost all part of other blocks, too, but what matters here is their role in the upper left of a block. (There are 97 of them because the three bottom rows and three right-most columns “start” blocks that extend off the edge of the rug, so we don’t count those.) Multiply 97 by 97, and you get 9,409 four-by-four blocks to use as a baseline for calculations.
The chances that any one of these blocks is all one color are the same as the chances that 15 of the squares in the four-by-four block match the color of the first upper-left square. With our three colors, that chance is equal to \((1/3)^{15}\). Therefore, the chance that there are no one-color blocks out of the 9,409 is \((1-(1/3)^{15})^{9,409}\), so the chance that there is a one-color block (and thus that the rug is rejected) is \(1-((1-(1/3)^{15})^{9,409})\), or about 0.0006555, or about our 0.066 percent.
The other way to get at this solution is to think about the whole universe of possible rugs. To do that, we have to determine the numerator (how many rejectable rug combinations there are) and the denominator (the number of total possible rug color combinations). The latter is easy to calculate: There are \({3^{100}}^2\) possible rugs (three colors to choose from, and 100 rows and columns of squares in each rug).
Figuring out the numerator is where it gets trickier. We need to consider every possible one-color block that will cause the rug to be rejected, along with every possible rug that includes that “bad” block. To do that, consider that there are \(97^2\) possible bad blocks, and three ways they each could be bad. Those bad blocks automatically make a rug a reject, but it matters what the rest of the rug looks like, since we are trying to do a full accounting of every possible rug. We can use our old denominator formula here, with one small tweak: \(3^{(100^2-16)}\), with the “16” representing the number of squares we know the color of already (the 4×4 reject block).
With all that in hand, we’re nearly done. Multiply the two elements of our numerator, and divide it over the denominator, and you get a formula for the proportion of rejected rugs: \((97^2\cdot 3)\cdot (3^{(100^2-16)})/({3^{100}}^2)\). That simplifies to \(97^2/3^{15}\), which is about 0.0006557, or again about our estimate of 0.066 percent.
And, as usual, you could also turn to a computer simulated approximation. Stephanie Valenzuela was kind enough to share her Python-based approach.
So how does this process scale? Riddler Rugs, I’m not ashamed to say, is in it for the money and has plans to produce way more than just one measly random rug. One rug’s not cool. You know what’s cool? A million rugs. And we’d prefer to not reject any, if we can help it.
Laurent Lessard plotted the probability of rejecting no rugs out of a million produced. With our initial three colors, we’re nearly sure to reject at least some rugs. But if we expanded our fabric palette to six or even seven colors — ROYGBIV, say — Riddler Rugs would have an excellent chance to produce a million rugs without rejecting even a single one.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.