This problem is based on a nice puzzle called “The Ice Cream Cake puzzle”. Its origin is unknown, but you can find it, for example, in Peter Winkler’s book “Mathematical Mind Benders”.
The main interesting thing about this problem is that – contrary to what many people intuitively expect – the answer is always finite, even if the step happens to be irrational. Yes, even if we never cut the circle twice in the same place, it will still always return to the all-black state after finitely many steps. We will now show why that is the case and also how to compute the minimal number of steps needed.
The key observation is that the locations of cuts don’t necessarily matter. After the cut, we always flip and reverse a part of the circle. If the reversal brings back a piece of the same color, the cut will, for all practical purposes, disappear – as if we never made it.
The only thing that matters are the coordinates at which a white piece touches a black piece. Below, we will call these coordinates borders.
Let’s change the game slightly. The new game will be completely equivalent to the old one, but it will be a bit easier to argue about it.
First of all, let’s scale everything. From now on, we’ll assume that the step length x is an arbitrary real from the open interval (0, 1), and that the circumference of the circle is exactly 1.1
The second change: instead of going around the circle, we will rotate the entire circle by x (measured along its circumference) after each flip. This way we’ll get an equivalent process, but we will always be making the cut at the same place, and we will always be flipping a wedge that lies on the same part of the table.
Imagine a fixed coordinate system around the circle. (I.e., the coordinates don’t rotate when the circle does, they are written on the table.) The coordinates wrap around the circle – i.e., all operations with them are done modulo 1. For example, the coordinates 0.47, 23.47 and −0.53 all represent the same point.
But back to our game. We will make the first cut at 0. Then, each round will consist of three steps:
The game is simple if the circumference is a positive multiple of x. If it happens to be the case that kx = 1 for a positive integer k, the game clearly ends after 2k steps: first we flip everything upside down in k steps and then we flip it back in another k steps.
Below, we will deal with the remaining case. Let k = ⌈1/x⌉.
If we start with an all-black circle, the first k − 1 cuts will flip a black wedge to its white side. Then, the k-th cut will cut into the first wedge.
Let’s write x = y + z, where y = 1/k. After the first round we have two borders: at 0 and at x. After the second round the borders are at 0 and 2x. After k − 1 rounds the borders are at 0 and (k − 1)x. In the following round we get a new border at x − kz. In the following rounds new borders appear at 2x − kz, 3x − kz, …, (k − 1)x − kz. And that’s it. We can easily show that if the current borders are only at some of these coordinates before a round, there will only be borders at some of these coordinates (and nowhere else) after the round.
The current state can be described by specifying the current set of borders and the color of one of the pieces between them. As there are only finitely many possible locations of borders, a state must eventually repeat. As the process is deterministic, it must be eventually periodic. And as the process is reversible, it must be purely periodic. Hence, the first state to repeat must be the initial state when the circle is all black.
The full set of border lines divides the circle into 2k − 1 areas. Out of those, k have length (x − kz) each, and between them (except for zero) k − 1 areas have length 4z. Let’s call the first ones “areas of type A” and the second ones “areas of type B”.
It is easy to show that areas of type A change their color periodically. As we do the rounds of our process, first we turn them from black to white, one at a time, and then we turn them back from white to black, one at a time. Thus, all areas of type A are black only once every 2k rounds.
The same holds for areas of type B. But as there is only k − 1 of those, they are only all black once every 2(k − 1) rounds.
It follows that the entire circle is black once every 2k(k − 1) rounds. (Note that k and k − 1 are relatively prime.)
In the task statement we just use some special values of x, but the proof and the algorithm work for all positive reals.↩