IMC 2013, Day 2, Problem 5
Consider a circular necklace with beads. Each bead can be painted either white or green. A painting of the necklace is called good, if among any successive beads there is at least one green bead. Prove that the number of good paintings of the necklace is odd.
(Two paintings that differ on some beads, but can be obtained from each other by rotating or flipping the necklace, are counted as different paintings.)
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
(Proposed by Vsevolod Bykov and Oleksandr Rybak, Kiev)
Solution 1. For denote by be the number of good open laces, consisting of (white and green) beads in a row, such that among any 21 successive beads there is at least one green bead. For all laces have this property, so for ; in particular, is odd, and are even.
For , there must be a green bead among the last 21 ones. Suppose that the last green bead is at the th position; then . The previous beads have good colorings, and every such good coloring provides a good lace of length . Hence,
Applying (1) again to the term ,
- is odd if or ;
- 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 white beads at the beginning and white beads at the end; then we have and , and we have a good open lace in the middle, between the first and the last green beads. That middle lace consist of beads. So, for any fixed values of and the number of such cases is .
[Figure in the original PDF.]
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
Solution 2 (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.
Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.