Can You Paint by Number?

You’re painting an infinite strip made of squares randomly numbered 0 or 1. How large is the average color cluster?

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. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.

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

I’m completing a paint-by-number painting, although this one is a little different from any that I’ve seen before. It’s an infinitely long strip of canvas that is 1 cm wide. It’s broken up into adjacent 1 cm-by-1 cm squares, each of which is numbered zero or one, each with a 50 percent chance. The squares are all numbered independently of each other. Every square with a zero I color red, while every square with a one I color blue.

Once I’m done painting, there will be many “clusters” of contiguous red and blue squares. For example, consider the finite strip of canvas below. It contains 10 total squares and seven clusters, which means the average size of a cluster here is approximately 1.43 squares.

Once I’m done painting, what will be the average size of each red or blue cluster?

Extra Credit

Once again, I’m painting an infinitely long strip of canvas, broken up into adjacent 1 cm-by-1 cm squares. Squares are randomly and independently numbered 0 or 1 as before. But this time, the strip itself is 2 cm wide.

Squares are considered adjacent if they share a common edge. So squares can be horizontally or vertically adjacent, but not diagonally adjacent.

Once I’m done painting, there will again be many “clusters” of contiguous red and blue squares. The example below contains 20 total squares and nine clusters, which means the average size of a cluster here is approximately 2.22 squares.

Once I’m done painting, what will be the average size of each red or blue cluster?

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 the existence of the AI Mathematical Olympiad. Why solve great mathematical puzzles when you can build an AI to solve them for you?

Okay, if you’re reading this, there’s a good chance you enjoy solving puzzles yourself. That said, this competition, which began earlier this week and is open to submissions for the next three months, is worth a look. LLMs have conquered various benchmarks that purport to assess intelligence, but math contest problems have proven relatively stubborn as they (in theory) require, well, mathematical reasoning.

At the time of this writing, Olga Tsymboi sits atop the leaderboard, having submitted code that solved 13 out of 50 AIME-style problems on a private test whose problems are not known to the public. In a word, that’s NUTS!

If you decide to take a three-month hiatus from reading this column in order to pursue the million-dollar prize pool, I won’t blame you. But just know that I’ll still be here every week, when you and your AI are ready to come back.

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.

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Lise Andreasen 🎻 from Valby, Copenhagen, Denmark. I received 65 timely submissions, of which 65 were correct—that marks the first time we hit 100 percent for a Fiddler! (Previously, two Extra Credits hit that milestone.) Really, really great work, everyone!

Last week, I had two large pitchers with known volumes: 10 liters (“pitcher A”) and 3 liters (“pitcher B”). They were both initially empty. I could do one of six things with the pitchers:

1. I could fill pitcher A to the top with water from the sink.

2. I could fill pitcher B to the top with water from the sink.

3. I could empty the contents of pitcher A into the sink.

4. I could empty the contents of pitcher B into the sink.

5. I could transfer the contents of pitcher A to pitcher B, until pitcher A was empty or pitcher B was filled to the top—whichever came first.

6. I could transfer the contents of pitcher B to pitcher A, until pitcher B was empty or pitcher A was filled to the top—whichever came first.

Every time I did any one of the above six, it counted as a step.

What was the fewest number of steps required until one of the pitchers (either A or B) contained precisely 5 liters of water?

Since 5 liters exceeded the volume of pitcher B (3 liters), the only way to reach the desired volume was to have it in pitcher A. To do this, the final move could have been a transfer from pitcher B (in which case the penultimate state was likely 2 liters in pitcher A and 3 liters in pitcher B) or a transfer from pitcher A (in which case the penultimate state was likely 8 liters in pitcher A and 0 liters in pitcher B).

Working forward from initially empty pitchers and backward from these target states revealed various pathways to 5 liters. But again, which of these required the fewest possible steps?

Solver Chengmin Yang achieved a volume of 5 liters in just 12 steps:

1. Fill pitcher B. (Status: A = 0, B = 3)

2. Transfer from pitcher B to pitcher A. (Status: A = 3, B = 0)

3. Fill pitcher B again. (Status: A = 3, B = 3)

4. Transfer from pitcher B to pitcher A again. (Status: A = 6, B = 0)

5. Fill pitcher B yet again. (Status: A = 6, B = 3)

6. Transfer from pitcher B to pitcher A yet again. (Status: A = 9, B = 0)

7. Fill pitcher B again (why not?). (Status: A = 9, B = 3)

8. Transfer from pitcher B to pitcher A, but this time you only transfer 1 liter to fill pitcher A. (Status: A = 10, B = 2)

9. Empty pitcher A (after all that work!). (Status: A = 0, B = 2)

10. Transfer from pitcher B to pitcher A. (Status: A = 2, B = 0)

11. Fill pitcher B one last time. (Status: A = 2, B = 3)

12. Transfer from pitcher B to pitcher A. (Status: A = 5, B = 0)

Solver Kiera Jones identified a second approach that worked in the same number of steps:

1. Fill pitcher A. (Status: A = 10, B = 0)

2. Transfer from pitcher A to pitcher B. (Status: A = 7, B = 3)

3. Empty pitcher B. (Status: A = 7, B = 0)

4. Transfer from pitcher A to pitcher B again. (Status: A = 4, B = 3)

5. Empty pitcher B again. (Status: A = 4, B = 0)

6. Transfer from pitcher A to pitcher B yet again. (Status: A = 1, B = 3)

7. Empty pitcher B yet again. (Status: A = 1, B = 0)

8. Transfer from pitcher A to pitcher B. (Status: A = 0, B = 1)

9. Fill pitcher A. (Status: A = 10, B = 1)

10. Transfer from pitcher A to pitcher B, but this time you only transfer 2 liters to fill pitcher B. (Status: A = 8, B = 3)

11. Empty pitcher B one last time. (Status: A = 8, B = 0)

12. Transfer from pitcher A to pitcher B. (Status: A = 5, B = 3)

Indeed, the fewest number of steps needed to reach a volume of 5 liters was 12, which was last week’s answer. A neat way to visualize this was to treat the volumes of water in pitchers A and B as an ordered pair, (A, B), and see which coordinates could be reached after each additional step.

For each of the six possible moves, at least one pitcher was made empty or made full. That meant the reachable coordinates had x-coordinates of 0 or 10 and/or y-coordinates of 0 or 3. In other words, they formed the perimeter of a rectangle.

Solver 🎬 Billy Mullaney 🎬 sketched out this rectangle, showing the transitions between coordinates as well as how many steps were needed to reach each of them. (Note that Billy used a slightly different coordinate system, with pitcher A’s volume top-to-bottom and pitcher B’s volume left-to-right.) Filling up or emptying the pitchers were indicated by the horizontal and vertical arrows, whereas transferring from one pitcher to another was indicated by the diagonal arrows. Starting from (0, 0) in the diagram, one can see that it took the maximum 12 steps to reach both (5, 0) and (5, 3).

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Andy Quick 🎻 from Kitchener-Waterloo, Canada. I received 38 timely submissions, of which 26 were correct—good for a 68 percent solve rate.

Instead of 10 liters and 3 liters, now the volumes of the pitchers A and B were 100 liters and 93 liters, respectively.

Suppose that the fewest number of steps needed until one of the pitchers (either A or B) contained precisely N liters of water was f(N), where N was a whole number between 1 and 100, inclusive.

What was the maximum value of f(N), and for which value of N did this occur?