Is the circle packing game equivalent to the circle packing problem?

119 Views Asked by At

I came up with the following impartial combinatorial game.

The game starts with an empty square with a given side length. The two players take turns, and in their turn, they place a circle of radius one somewhere inside the square. The circle may not overlap with any of the previously placed circles. The game ends when there is no more room for a circle.

Under normal play, so if the last player to place a circle wins, we can try to calculate the Grundy value as a function of the side length. If a maximum of $n$ circles fit inside the square, then there can be at most $n$ moves, so the Grundy value is at most $n$. My question is whether the Grundy value is always equal to $n$.

I have verified this hypothesis to be true for the smallest side lengths allowing two, three, four and five circles. I have not verified it for side lengths in between, or for larger side lengths. I personally do not expect the hypothesis to hold for all side lengths.

Note that determining whether the Grundy value of a game is equal to the maximum number of moves $n$ is easier than calculating the Grundy value in general. You only need to check for all values less than $n$ whether there is a move that produces that Grundy value. It is already certain that there is no move that produces Grundy value $n$. So you only need to show that certain moves exist, and not that certain moves do not exist.

This property does not necessarily hold for deeper levels of the game though. For example, with the smallest square that fits five circles, you can not place the first circle such that there are no more moves left, but placing the first circle in the center still produces Grundy value zero. Actually, placing the first circle in the center produces Grundy value zero for any side length, because you can do a mirroring strategy.

My working out for the mentioned side lengths is simply a large collection of moves, so I do not think they are worth sharing. I expect anyone with a chance of solving the problem should be able to come up with the moves themselves anyways. Especially the first two are really easy.

1

There are 1 best solutions below

0
On

Like you, I expect that the Grundy value is sometimes smaller than the maximum number of circles that will fit. The case with n=5 is not large enough to see the general behavior.

The case with n=9 (a 6×6 square) is much more likely to furnish a counter-example. Placing circles around the edges of the square leaves large Grundy values, but it is not at all clear that you leave Grundy value 1 or 2 or 3 after just one move.