Can You Pack the Circles?

The most efficient way to pack circles is hexagonally. Except for when it’s not.

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

You want to pack four rows of unit circles into a rectangle with a base of 8. You’re considering two strategies for packing:

1. Square packing. In this case, four rows of circles each are packed in an array of squares.

2. Hexagonal packing. In this case, the bottom row has four circles, and higher rows alternate between having three and four circles.

The following diagram shows the square-packed and hexagonal-packed rectangles on the left and right, respectively:

While the bases of both rectangles are 8, their heights are as small as possible such that the circles all fit.

Which packing strategy—square or hexagonal—is more efficient for packing these four rows? In other words, which packing results in a greater number of circles packed per unit of rectangular area?

This Week’s Extra Credit

Over large spaces, hexagonal packing of unit circles is more efficient than square packing. But instead of a large space, suppose you have an 8×k rectangle.

Assume that both packing strategies start with four circles on the bottom row of the rectangle. Square packing adds additional rows of four circles, one on top of the other, until there is insufficient room at the top of the rectangle. Meanwhile, hexagonal packing adds additional rows that alternate between three and four circles, one on top of the other, until there is insufficient room at the top of the rectangle. Here are diagrams of both packing strategies in an 8×k rectangle (note that the hexagonal-packed rectangle can have either three or four circles in the top row):

At some point, hexagonal packing will always be more efficient than square packing. What is the minimum value of k such that, for all heights greater than or equal to k, hexagonal packing is strictly more efficient than square packing?

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. Last week, I shared one of my favorite problems from the 2024 American Regions Mathematics League (ARML), one of the largest in-person high school math competitions in the country, where I was a guest lecturer.

This week, I’m sharing another one of my favorites from the competition, but this time it’s from something called the “Power Round.” ARML Power Rounds are legendary—they consist of several related proofs of increasing complexity. What’s more, they are completed by teams, with teammates coordinating and scrambling to write up these proofs over the course of a fleeting 60 minutes.

This year’s Power Round, titled “The Rainbow Connection” (sadly, there were plenty of students who didn’t get the reference), involved coloring the integers. From the Power Round itself:

For a positive integer r, define an r-coloring of a subset S of the integers to be a coloring of the elements of S that uses exactly r distinct colors, each color being used at least once.

Through the round, students had to prove or disprove the statements about “rainbow” arithmetic progressions:

Given a coloring of a set of integers, a rainbow arithmetic progression is a subset of those integers whose elements are all different colors and form an arithmetic progression.

For example, suppose the positive integers are 3-colored (red, green, and blue), and that 1, 4, and 7 are red, 2 and 5 are green, and 3 and 6 are blue. Then {2, 4, 6} is a rainbow arithmetic progression—all three colors are represented, and the numbers form an arithmetic progression.

With these definitions out of the way, here was Problem 7 (of 12) from the Power Round:

(a) Find a 3-coloring of the set of positive integers such that there is no rainbow arithmetic progression of length 3.

(b) Is there a positive integer r such that every r-coloring of the set of positive integers must contain a rainbow arithmetic progression of length 3? Either find the least such r or prove that no such r exists.

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: 🎻 Adnan Haque 🎻 from New York. I received 44 timely submissions, of which 38 were correct—good for an 86 percent solve rate.

Last week’s puzzle was inspired by ESPN’s reporting on the Boston Celtics’ comebacks against the Indiana Pacers:

You were asked to explore a toy version of basketball, in which you were playing a game with five “possessions.” For each possession, there was a 50 percent chance that your team scored one point. If you didn’t score, then your opponent instead scored one point.

After the game, ESPN reported that your opponent’s chances of winning were “75 percent chance or higher” at some point during the game (i.e., before the final possession was complete).

Given this information, what was the probability that your team actually won the game?

If your opponent had a 75 percent chance of winning, that suggested your team had a 25 percent chance of winning, right? Just to be sure, let’s work through the math in a little more detail.

A good first step was to determine how likely your opponent’s victory was from any given possible score in the game. And to do that, you had to work backwards. For starters, you knew what your opponent’s chances of winning were for each of the six possible final scores (as a convention, I list your score followed by your opponent’s):

• (0, 5): 100 percent chance your opponent wins.

• (1, 4): 100 percent chance your opponent wins.

• (2, 3): 100 percent chance your opponent wins.

• (3, 2): 0 percent chance your opponent wins.

• (4, 1): 0 percent chance your opponent wins.

• (5, 0): 0 percent chance your opponent wins.

Well, that wasn’t particularly illuminating. But these figures allowed you to compute your opponent’s chances of winning after four possessions. For example, if the score was (2, 2) after four possessions, then there was a 50 percent chance the score after the next possession would be (2, 3) and a 50 percent chance it would be (3, 2). Averaging your opponent’s chances for those two scenarios gave you their chance of winning when it was (2, 2). In general, if the current score was (i, j), then your opponent’s chances of winning, p(i, j), were equal to p(i+1, j)/2 + p(i,j+1)/2. So after four possessions, the possible scores were:

• (0, 4): 100 percent chance your opponent wins.

• (1, 3): 100 percent chance your opponent wins.

• (2, 2): 50 percent chance your opponent wins.

• (3, 1): 0 percent chance your opponent wins.

• (4, 0): 0 percent chance your opponent wins.

Continuing to work backwards, the possible scores after three possessions were:

• (0, 3): 100 percent chance your opponent wins.

• (1, 2): 75 percent chance your opponent wins.

• (2, 1): 25 percent chance your opponent wins.

• (3, 0): 0 percent chance your opponent wins.

Here, the 75 percent was the average of 50 and 100 percent, while the 25 percent was the average of the 0 and 50 percent. Next, the possible scores after two possessions were:

• (0, 2): 87.5 percent chance your opponent wins.

• (1, 1): 50 percent chance your opponent wins.

• (2, 0): 12.5 percent chance your opponent wins.

And the possible scores after one possession were:

• (0, 1): 68.75 percent chance your opponent wins.

• (1, 0): 31.25 percent chance your opponent wins.

Finally, the only possible score after zero possessions was:

• (0, 0): 50 percent chance your opponent wins.

Instead of bulleted lists, a better way to organize all this data was via a table, as shown below. Each cell in the table—other than the final scores—is the average of the cell directly below it and the cell to its right.

As a reminder, your task was to find the probability that your team won, given that your opponent had at least a 75 percent chance of winning at some point prior to the end of the game. That meant the answer was a fraction whose denominator was the number of paths through the above grid where your opponent had at least a 75 percent chance of winning before the end, while the numerator was those among the aforementioned paths that ended with a victory for you.

Now, I took the liberty of highlighting two specific cells in the grid above. For your opponent to have a 75 percent or greater chance of winning at some point during the game, exactly one of these cells must have been visited (note that they couldn’t both have been visited). Therefore, the answer’s denominator was the number of paths that went through either of these two cells.

How many paths went through (0, 3)? There was only one way to get there, and then four ways the final two possessions could have gone. That meant there were 1·4, or four such paths. And how many paths went through (1, 2)? There were three ways to get there, and again four ways the final two possessions could have gone. That meant there were 3·4, or 12 such paths. Altogether, there were 4+12, or 16 paths in which your opponent had at least a 75 percent chance of winning.

And how many of those 16 paths resulted in a victory for your team? Passing through (0, 3) was a guaranteed loss for you, which meant the game had to pass through (1, 2). From there, the path had to head straight down to reach (3, 2) and a victory for you. As we already said, there were three ways to go from (0, 0) to (1, 2), which meant the numerator was three. The three paths that resulted in victory for you, despite a 75 percent chance of swinging the other way, were:

• (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) → (3, 2)

• (0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) → (3, 2)

• (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2) → (3, 2)

Putting the numerator and the denominator together, if your opponent had at least a 75 percent chance of winning at some point during the game, your team’s probability of winning was 3/16, or 18.75 percent. This turned out to be quite a bit less than the 25 percent one might have initially expected!

(Note: I also gave full marks to answers of 13/16, or 81.25 percent. This was in fact your opponent’s chances of winning.)

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Izumihara Ryoma 🎻 from Toyooka, Japan. I received 16 timely submissions, of which 10 were correct—good for a 62.5 percent solve rate. This was a tough one!

For Extra Credit, instead of five possessions, now there were 101. Again, with each possession, there was a 50 percent chance that your team scored one point. If you didn’t score, then your opponent instead scored one point.

After the game, ESPN reported that your opponent’s chances of winning were “90 percent chance or higher” at some point during the game (i.e., before the final possession was complete).

Given this information, what was the probability that your team actually won the game?