Problem

Source: Serbia TST 2022/3

Tags: combinatorics, number theory, double counting



Let $n$ be an odd positive integer. Given are $n$ balls - black and white, placed on a circle. For a integer $1\leq k \leq n-1$, call $f(k)$ the number of balls, such that after shifting them with $k$ positions clockwise, their color doesn't change. a) Prove that for all $n$, there is a $k$ with $f(k) \geq \frac{n-1}{2}$. b) Prove that there are infinitely many $n$ (and corresponding colorings for them) such that $f(k)\leq \frac{n-1}{2}$ for all $k$.