IMC 2013 · Day 2 · P10

For $k = 0, 1, \dots$ denote by $N_k$ be the number of good open laces, consisting of $k$ (white and green) beads in a row, such that among any 21 successive beads there is at least one green bead. For $k \le 21$ all laces have this property, so $N_k = 2^k$ for $0 \le k \le 20$; in particular, $N_0$ is odd, and $N_1, \dots, N_{20}$ are even.

For $k \ge 21$, there must be a green bead among the last 21 ones. Suppose that the last green bead is at the $\ell$th position; then $\ell \ge k - 20$. The previous $\ell - 1$ beads have $N_{\ell-1}$ good colorings, and every such good coloring provides a good lace of length $k$. Hence, $$\tag{1} N_k = N_{k-1} + N_{k-2} + \dots + N_{k-21} \quad \text{for } k \ge 21.$$ From (1) we can see that $N_{21} = N_0 + \dots + N_{20}$ is odd, and $N_{22} = N_1 + \dots + N_{21}$ is also odd.

Applying (1) again to the term $N_{k-1}$, $$N_k = N_{k-1} + \dots + N_{k-21} = \bigl( N_{k-2} + \dots + N_{k-22} \bigr) + N_{k-2} + \dots + N_{k-21} \equiv N_{k-22} \pmod 2$$ so the sequence of parities in $(N_k)$ is periodic with period 22. We conclude that

• $N_k$ is odd if $k \equiv 0 \pmod{22}$ or $k \equiv 21 \pmod{22}$;
• $N_k$ is even otherwise.

Now consider the good circular necklaces of 2013 beads. At a fixed point between two beads cut each. The resulting open lace may have some consecutive white beads at the two ends, altogether at most 20. Suppose that there are $x$ white beads at the beginning and $y$ white beads at the end; then we have $x, y \ge 0$ and $x + y \le 20$, and we have a good open lace in the middle, between the first and the last green beads. That middle lace consist of $2011 - x - y$ beads. So, for any fixed values of $x$ and $y$ the number of such cases is $N_{2011-x-y}$.

It is easy to see that from such a good open lace we can reconstruct the original circular lace. Therefore, the number of good circular necklaces is $$\sum_{x+y \le 20} N_{2011-x-y} = N_{2011} + 2 N_{2010} + 3 N_{2009} + \dots + 21 N_{1991} \equiv N_{2011} + N_{2009} + N_{2007} + \dots + N_{1991} \pmod 2.$$ By $91 \cdot 22 - 1 = 2001$ the term $N_{2001}$ is odd, the other terms are all even, so the number of the good circular necklaces is odd.

(by Yoav Krauz, Israel) There is just one good monochromatic necklace. Let us count the parity of good necklaces having both colors.

For each necklace, we define an adjusted necklace, so that at position 0 we have a white bead and at position 1 we have a green bead. If the necklace is satisfying the condition, it corresponds to itself; if both beads 0 and 1 are white we rotate it (so that the bead 1 goes to place 0) until bead 1 becomes green; if bead 1 is green, we rotate it in the opposite direction until the bead 0 will be white. This procedure is called adjusting, and the place between the white and green bead which are rotated into places 0 and 1 will be called distinguished place. The interval consisting of the subsequent green beads after the distinguished place and subsequent white beads before it will be called distinguished interval.

For each adjusted necklace we have several necklaces corresponding to it, and the number of them is equal to the length of distinguished interval (the total number of beads in it) minus 1. Since we count only the parity, we can disregard the adjusted necklaces with even distinguished intervals and count once each adjusted necklace with odd distinguished interval.

Now we shall prove that the number of necklaces with odd distinguished intervals is even by grouping them in pairs. The pairing is the following. If the number of white beads with in the distinguished interval is even, we turn the last white bead (at the distinguished place) into green. The white interval remains, since a positive even number minus 1 is still positive. If the number of white beads in the distinguished interval is odd, we turn the green bead next to the distinguished place into white. The green interval remains since it was even; the white interval was odd and at most 19 so it will become even and at most 20, so we still get a good necklace.

This pairing on good necklaces with distinguished intervals of odd length shows, that the number of such necklaces is even; hence the total number of all good necklaces using both colors is even. Therefore, together with monochromatic green necklace, the number of good necklaces is odd.