$n$ coins lies in the circle. If two neighbour coins lies both head up or both tail up, then we can flip both. How many variants of coins are available that can not be obtained from each other by applying such operations?
Problem
Source: St Petersburg Olympiad 2018, Grade 10, P3
Tags: combinatorics
abeker
16.07.2018 02:24
We claim that the answer is $2$ for $n$ odd and $n + 1$ for $n$ even. Label the heads/tails with zeros/ones to get a cyclic binary sequence.
First consider the case when $n$ is odd. Then the sum of the numbers is invariant modulo $2$, so there are at least two equivalence classes. It therefore suffices to show that we can always obtain a constant sequence by applying the operations. So suppose we have a non-constant sequence and divide it into maximal contiguous blocks of equal elements. Then we must have an even number of blocks, so there exists a block of even length (otherwise the sum of the lengths of the blocks would be even). So we can flip all the values in that block and thus decrease the total number of blocks. By repeating this operation, we can eventually obtain a constant sequence.
Now suppose that $n$ is even. Then the given binary sequence $a_1, a_2, \ldots, a_n$ uniquely correponds to the binary sequence $b_1, b_2, \ldots, b_n$ with $b_i \equiv a_i + i \pmod 2$ for all $i$. Note that an operation consists of choosing two distinct neighbouring elements of this sequence and swapping them. Hence, two sequences are equivalent iff they are permutations of each other, i.e. have the same number of ones. It follows that there are $n + 1$ equivalence classes, as claimed.