We call the arrangement of $n$ ones and $m$ zeros around the circle as good, if we can swap neighboring zero and one in such a way that we get an arrangement, that differs from the original by rotation. For what natural $m$ and $n$ does a good arrangement exist?
Problem
Source: Moscow Olympiad 2018, Grade 10, P4
Tags: combinatorics
13.08.2022 17:50
We claim that such an arrangement exists only for coprime $m,n$. Assign a number from $0,1,\ldots,m+n-1$ to the positions on the circle clockwise. Construction: Say $m,n$ are coprime. Then $n$ and $m+n$ are also coprime. Then $$nk\pmod{m+n} \textrm{ for } k\in{0,1,\ldots,m+n-1} \textrm{ gives pairwise distinct remainders.}$$There exists $k_0$ such that $nk_0 \equiv 1\pmod{m+n}$. Putting $1$ on the positions of the remainders of $$k_0, 2k_0, \ldots,nk_0\equiv1\pmod{m+n}$$and zero otherwise, then for a rotation by $k_0$ the the ones transfer to positions of the remainders of $$0, k_0, 2k_0, \ldots,(n-1)k_0\equiv1\pmod{m+n}$$meaning the $1$ at position one swaps with the $zero$ at position zero implying that this is a good arrangement. Proof: Say that $\gcd{(m,n)}=d>1$. Consider the remainder, which gives the sum of the position numbers of units when divided by $d$. When a rotation is made by $k$, each number is incremented by $k$ modulo $m+n$ meaning that the sum of all numbers increases by $kn$ and decreases by some multiple of $m+n$ implying that the remainder remains invariant modulo $d$. But if an adjacent zero and one are swapped the remainder changes (by exactly 1) implying that an arrangement that differs from the original one by a rotation cannot be obtained. This finishes the proof.