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,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
Alex Bellos, who writes the excellent math puzzle column at The Guardian, has a new book out called “Can You Solve My Problems?” He was kind enough to donate two of his problems to The Riddler this week. First up, an equatorial puzzle:
A rope lies tightly around the circumference of the Earth. The rope is then extended in length by 1 meter and raised up at every point from the ground until it is again a taut circle, and every point on the rope is the same height above the ground.
How high is the rope off the ground now?
Riddler Classic
Also from Alex, a space race:
Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only condition being that the coins are not allowed to touch. The winner is the person who places the final coin on the table, meaning that he or she fills the last remaining space between the other coins.
The table has to be larger than a single coin, and all the coins placed must be identically sized.
One player is always guaranteed to win if they use a certain strategy. Which one is it — the one who starts or the one who goes second? And what is his or her strategy?
Solution to last week’s Riddler Express
Congratulations to 👏 Marc Broering 👏 of Louisville, Kentucky, winner of last week’s Express puzzle!
You were given a budget of 10 characters, and asked to write down the largest number you could. Four numbers were by far the most commonly submitted: 9!!!!!!!!!, 9^9^9^9^9!, 9^9^9^9^99 and 9^99999999. (The caret (^) raises a number to a power and the exclamation point is the factorial.) All of these are unfathomably large, but some are unfathomably larger than others. Let’s compare.
The smallest of these is 9^99999999. (For scale, this works out to roughly a meager \(10^{95,424,250}\).) But that’s not the most efficient exponent path. The exponent (99999999) is smaller than 9^9 (387,420,489), so you’d do better to spend your characters on power-raising rather than extra 9s. Which brings us to 9^9^9^9^99, but that’s not the best either because 9! is much larger than 99, so we’d do better to spend that last digit on a factorial than an extra 9. But which is larger: 9^9^9^9^9! or 9!!!!!!!!!?
According to the HyperCalc, 9!!!!!!!!! is the large-number champ. It evaluates to something like
\begin{equation}10^{{10}^{{10}^{{10}^{{10}^{{10}^{{10}^{{10}^{1,859,939}}}}}}}}\end{equation}
while 9^9^9^9^9! evaluates to “just” something like
\begin{equation}10^{{10}^{{10}^{{3\cdot 10^{346,275}}}}}\end{equation}
(In “comparison,” the number of atoms in the universe is embarrassingly minuscule: Something like \(10^{80}\).)
But with some more exotic notation we can do even better. While addition (+), multiplication (×), exponentiation (^) and factorialization (!) are widely known, there are other operations that mathematicians have invented that could make our numbers even larger even faster. One of these is the Knuth up-arrow notation, denoted by ↑. With this notation, 3^3^3^3^3, for example, can be represented economically as 3↑↑5. This notation is often used to define Graham’s number, which is said to be the largest number ever used in a mathematical proof.
Another is the Conway chained-arrow notation, denoted by →. With this notation, x→y→z, for example, equals x↑↑↑…↑↑↑y, with z Knuth up-arrows in the middle. Something like 9→9→9→9→9!, which a number of solvers submitted, is unfathomably, abysmally, eternally, incomprehensibly large.
Solution to last week’s Riddler Classic
Congratulations to 👏 Aaron Cote 👏 of Los Angeles, winner of last week’s Classic puzzle!
You and a robot friend are trapped somewhere in a corn maze. The maze is a 10-by-10 grid of cells, surrounded by walls, and with walls separating certain pairs of cells. Your goal is to reach an “end square,” upon which flares will shoot up and you’ll be saved. You’re too tired to walk, but you can program your robot to walk any number and combination of steps — north, south, east and west. If the robot bumps into a wall, it simply moves on to the next directional instruction you’ve given it. What instructions do you feed your robot to guarantee that it will reach the end square somewhere along its journey?
This turned out to be another large-number problem in disguise. As the puzzle’s submitter, Robbie Ostrow, explained, none of the immediately obvious ideas work. There is no trick. It’s easy to construct a dastardly maze in which the robot gets stuck when you attempt some clever variation of rotating directions, or sticking to the left wall, etc. The only way to do it is, essentially, to feed the robot the solution to every possible maze (more on how many there are in a moment).
Here’s how Robbie described the inefficient, but guaranteed-to-find-a-path, algorithm:
- Let W be the set of all possible mazes, each uniquely defined by the positions of the walls (w), the start position (s) and the end position (f). Every element of W is defined by a list (w, s, f).
- Write down W.
- Let L be the list of moves, currently empty.
- For each maze, m, in W: Apply all the moves in L to m. (I.e. if m is the true configuration of the maze, this gives you your current position s’.) Now, solve the maze (w, s’, f) and append the solution to L.
- Give L to the robot.
It’ll get there … eventually. We never said you’d still need to be alive when it reached the destination!
How many instructions will you have to give the robot? A lot. Here’s how to calculate an upper bound on the minimum number of instructions: There are \(2\cdot 9\cdot 10 = 180\) places to put an interior wall. There are 9,900 different ways to pick the starting and ending squares (there are 100 places to put the first square, and 99 places to put the second — multiply those against each other and you’ll find the number of possible combinations for the starting and ending square). Because of the size of the maze, a solution is at most 99 moves long — walking through every cell. Multiplying all those possibilities together leaves you with an upper bound of \(9,900\cdot 99\cdot 2^{180}\) (or about \(1.5\cdot 10^{60}\)) instructions that you have to give to the robot. You can likely pare down these possible instructions by looking for symmetries, eliminating some possible mazes and so forth, but the road will nevertheless be very, very long.
Good luck out there, little robot. And make sure to tell people how to find us when you get out.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.