Arranging $9$ numbers around a circle

Question

I am trying to solve the below problem.

Suppose that five $1$s and four $0$s are arranged around a circle. Form a new circle by placing a $0$ between any two unequal adjacent numbers and a $1$ between any two equal values before then erasing the original values. Show that, no matter how many times you repeat this and no matter what the initial configuration is, you will never get a circle of all $0$s.

Below is my attempt.

Fix an initial configuration on the circle arranged around the circle in a counterclockwise manner beginning at the ``12:00'' position. If it were possible to construct a new circle of all $0$s, it must be the case that the configuration of the original circle alternated fully. However, if the configuration began with a $0$, it cannot alternate fully because $9$ is odd and therefore we have an uneven number of $1$s and $0$s. Indeed, if we attempt to alternate fully upon beginning with a $1$, the best we can do is $101010101$, though our first and last elements of the configuration are $1$s. Alternatively, if we began with a $0$, the best we can do is $010101011$ since we have only four $0$s to work with. In either case, we cannot fully alternate $0$s and $1$s in our initial arrangement, so there is no way to create a new circle composed entirely of $0$s.

What I think I want to say is that $9$ is odd, so there are an uneven number of $0$s and $1$s so any attempt will fail. I'm not sure if the language I used to the effect of "the best we can do" makes total sense, because I could have a repeat somewhere else. What I was trying to say was, let's fix a starting point and attempt to create a circle that fully alternates, and no matter whether that start is a $0$ or a $1$, we eventually run into the issue of a repeat somewhere, particularly a repeated $1$. I'm not sure if it's a repeated $1$ in every case, but I expect that to be the case.

Is there a "more general" argument for this? Especially since the problem says "no matter what the initial configuration is," I think the argument I presented is too hand-wavy and not general enough.

Answer 1

I think your argument is just fine - to get all zeros you will need the previous state to be fully alternating between 0 and 1, and that is not possible with an odd-sized circle.

Here is another proof. If you go around the circle once, counting the number of times it changes from 0 to 1 and also the number of times it changes from 1 to 0, then those two counts must be equal because when going around the circle you end on the same digit you started with. Therefore the number of zeros will always be even (except maybe the starting configuration), and you can never get nine zeros.

Answer 2

Yet another argument: Swap the roles of $1$ and $0$ completely in the problem. At each stage you will get a circle that is just the complement of the one in this problem.

But now, working modulo $2$, each new number is the sum of the two values it is inserted between. If you sum all the numbers after the replacement, you get twice the sum of the numbers before replacement, as each of them contributes to the replacement values on each side. Modulo $2$, that sum will aways be $0$.

No matter your original configuration of $1$s and $0$s, the sum of the values after a replacement is always $0$. Since nine $1$s sums to $1$, the only way to get it is to have it as the starting configuration. More generally you cannot any odd number of $1$s except in the original configuration.

Translating back to the unswapped problem: The only time you can ever have an odd number of $0$s is in the original configuration.

---

Effectively this is the same solution as Jaap Scherphuis, but I offer it because the more complicated mechanism here may generalize to related questions more easily.

Answer 3

As a more general and concise argument, you can approach like this:

Placing a $0$ between two unequal numbers preserves the number of $0$ present in the circle. Placing a $1$ between two equal numbers preserves the parity of the number of $0$. Because there are an even number of $0$s initially, we can not have an odd number of $0$s at the end. Thus, there can't be $9$ zeros in the circle.