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$.
Problem
Source: Serbia TST 2022/3
Tags: combinatorics, number theory, double counting
28.05.2022 13:22
Part a). Note that $\displaystyle \sum_{k=1}^{n-1}f(k)$ equals the number of ordered pairs $(b_1,b_2)$, where $b_1,b_2$ are distinct balls of the same color. Let $\ell$ be the number of the white balls. Hence, $$\sum_{k=1}^{n-1}f(k)=\ell(\ell-1)+(n-\ell)(n-\ell-1)\qquad (1)$$The RHS attains its minimum, when $\ell=\lfloor n/2\rfloor$. Assume now, for the sake of contradiction, $ f(k)<\frac{n-1}{2},\forall k, 1\le k\le n-1$. We should consider two cases 1) $n$ is odd. In this case we have $f(k)\le (n-2)/2, k=1,2,\dots,n-1$. Further, $(1)$ yields $$\frac{(n-1)(n-2)}{2}\ge \frac{n(n-2)}{2}$$which is contradiction. The case $n$ is odd is similar.
28.05.2022 17:22
Part b) would be hard if the tags didn't spoil everything. Just take p=3(mod 4) and the i th ball is black iff i=0 or i is a NQR in modulo p.
13.02.2024 21:10
VicKmath7 wrote: 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$. I think in the official pdf, there exists a sentence at the beginning: Нека је $n$ непаран (odd) природан број. Here the $n$ should be an odd natural number.
13.02.2024 23:49
See this as well as USA TSTST 2016/3. In general, 3 mod 4 primes' QRs having constant overlap when shifted is a somewhat well-known fact
09.05.2024 18:26
The problem was also spoiled to me on the actual test since the National MO had a combo P3 and all subjects have 3 problems over the 4 tests, so I knew it had to do with QRs...