Can You Tip the Dominoes?

You’re placing dominoes one at a time. Each one has a small chance of causing a chain reaction. After countless attempts, what’s the median number of dominoes before a chain reaction?

Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of myself and Ollie Roeder.

Each week, I present mathematical puzzles intended to both challenge and delight you. Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “Extra Credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.

I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.

This Week’s Fiddler

Inspired by some truly incredible domino construction, Ed Foley poses the following puzzle:

You are placing many, many dominoes in a straight line, one at a time. However, each time you place a domino, there is a 1 percent chance that you accidentally tip it over, causing a chain reaction that tips over all dominoes you’ve placed. After a chain reaction, you start over again.

If you do this many, many times, what can you expect the median (note: not the average) number of dominoes placed when a chain reaction occurs (including the domino that causes the chain reaction)? More precisely, if this median number is M, then you would expect to have placed fewer than M dominoes at most half the time, and more than M dominoes at most half the time.

This Week’s Extra Credit

You’re placing dominoes again, but this time the probability of knocking each domino over and causing a chain reaction isn’t 1/100, but rather 10^-k, where k is a whole number. When k = 1, the probability of knocking over a domino is 10 percent; when k = 2, this probability is 1 percent; when k = 3, this probability is 0.1 percent, and so on.

Suppose the expected median number of dominoes placed that initiates a chain reaction is M. As k gets very, very large, what value does M/10^k approach?

Making the ⌊Rounds⌉

There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing some new puzzles invented by Alf Smith and described by Alex Bellos over at The Guardian.

I’ve been doing a lot of Sudokus recently, and I think I’ve gotten pretty decent at solving them. That means when a new variation comes along, I pay attention. Alf’s variation includes no initial numbers. Instead, some squares are colored gold. These gold squares must contain a number that represents the row of that square (top-to-bottom), the column of that square (left-to-right), or the placement of that square within its box (left-to-right, then top-to-bottom). White squares, on the other hand, cannot contain any of these numbers.

Alex walks us through the following 6×6 grid:

Spoiler alert! Here’s the solution, which I very much enjoyed working out for myself:

Now, see if you can solve the two remaining 9×9 grids that Alex provides.

Want to Submit a Puzzle Idea?

Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.

Standings

I’m tracking submissions from paid subscribers and compiling a leaderboard, which I’ll reset every quarter. All timely correct solutions to Fiddlers and Extra Credits are worth 1 point each. At the end of each quarter, I’ll 👑 crown 👑 the finest of Fiddlers. (If you think you see a mistake in the standings, kindly let me know.)

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 “Maths ForFun” 🎻 from the Pacific Northwest. I received 65 timely submissions, of which 48 were correct—good for a 74 percent solve rate.

Last week, I had a hat with six small toy rabbits: two were orange, two were green, and two were purple. I shuffled the rabbits around and randomly drew them out one at a time without replacement (i.e., once I drew a rabbit out, I never put it back in again).

Your job was to guess the color of each rabbit I drew out. For each guess, you knew the history of the rabbits I had already drawn. So if we were down to the final rabbit in the hat, you should have been able to predict its color with certainty.

Every time you correctly predicted the color of the rabbit I drew, you earned a point. If you played optimally (i.e., to maximize how many points you got), how many points could you have expected to earn on average?

Since there were two rabbits of each color, it didn’t matter which color you chose first. No matter what, your probability of choosing correctly was 1/3, which meant you could expect to earn 1/3 points on your first guess.

From there, things got trickier. For convenience, let’s define A as the number of rabbits for the most common remaining color, B as the number of rabbits for the next most common remaining color, and C as the number of rabbits for the least common remaining color. Note that A ≥ B ≥ C. Finally, let’s define E(A,B,C) as your expected number of points for particular values of A, B, and C.

The puzzle was essentially asking for the value of E(2,2,2). So far, we found that E(2,2,2) = 1/3 + E(2,2,1).

At this point, you had two rabbits of one color, two rabbits of another color, and one rabbit of the remaining color (the color that was selected first). The probability that the next rabbit drawn was the first color was 2/5, the probability for the second color was also 2/5, and the probability for the remaining color was 1/5. Your best bet was to pick one of the first two colors. So there was a 2-in-5 chance you got a point and found yourself in the state (A,B,C) = (2,1,1), a 2-in-5 chance you didn’t get a point and found yourself in that same state, and a 1-in-5 chance you guessed incorrectly and found yourself in the state (2,2,0).

Mathematically, this could be written as E(2,2,1) = 2/5 · (1 + E(2,1,1)) + 2/5 · E(2,2,1) + 1/5 · E(2,2,0) = 2/5 + 4/5 · E(2,1,1) + 1/5 · E(2,2,0). From there, you still had to work out the values of E(2,1,1) and E(2,2,0). The latter was a little easier (in my opinion) to compute, since it involved only two remaining colors. With some more casework, E(2,2,0) came out to 17/6.

When faced with the state (2,1,1), your best bet was to guess the color that still had two rabbits, and you were right with probability 1/2. Mathematically, E(2,1,1) = 1/2 + 1/2 · E(1,1,1) + 1/2 · E(2,1,0). That last term, E(2,1,0), involved two colors again, and came out to be 7/3. Meanwhile, E(1,1,1) involved three rabbits, one of each color. There was a 1-in-3 chance you got that first one right, then a 1-in-2 chance you got the second one right, and a 1-in-1 (woohoo!) chance you got the last one right, for a total expectation of 11/6 points.

Putting this all together, E(2,1,1) = 1/2 + 1/2 · 11/6 + 1/2 · 7/3 = 31/12. Working backwards, that meant E(2,2,1) = 2/5 + 4/5 · 31/12 + 1/5 · 17/6 = 91/30. Finally, E(2,2,2) = 1/3 + 91/30 = 101/30. And that was the answer! On average, you could expect to earn 101/30, or about 3.37 points.

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Adam D 🎻 from London, United Kingdom. I received 39 timely submissions, of which 37 were correct—good for a 95 percent solve rate.

Now, instead of two rabbits of each of the three colors, my hat contained 10. That is, it contained 10 orange rabbits, 10 green rabbits, and 10 purple rabbits. As before, every time you correctly predicted the color of the rabbit I drew, you earned a point.

With optimal play, how many points could you have expected to earn on average?