Let $n$ be a non-zero natural number, $n \ge 5$. Consider $n$ distinct points in the plane, each colored or white, or black. For each natural $k$ , a move of type $k, 1 \le k <\frac {n} {2}$, means selecting exactly $k$ points and changing their color. Determine the values of $n$ for which, whatever $k$ and regardless of the initial coloring, there is a finite sequence of $k$ type moves, at the end of which all points have the same color.
Problem
Source: 2010 Romania JBMO TST 1.5
Tags: Coloring, combinatorial geometry, combinatorics, points
07.10.2020 20:31
Let these colors be $0$ and $1$ and also just think of them as an array. Checking small cases it's easy to see $n$ odd is good, and $n$ even is bad. Firstly, I'll prove that $n$ even does not work for all $k$. Let #$0$ be the number zeroes and #$1$ be the number of ones. Obviously #$0+$#$1=n$. If for $n$ even we have #$ 0$ is odd then we have #$1$ is odd. When we choose $k=2$ we have after switching some $0$ to $1$ or vice versa the parity of #$0$ and #$1$ stays the same. Since at the beginning we had #$0$ and #$1$ were odd, at the end they should be both even so this is impossible. Now we show that $n$ odd is possible always. We proceed with induction. It is easy to check $n=5$. Assume we are given an array of zeroes and ones $000....0001111....111$. If $k<\frac{n-1}{2}$ we can flip the bits into $00111....111$ ($n-2$ ones) or into $00 00...000$ ($n-2$ zeroes) but in the second case we're done. So we only need to check the first case. The construction goes in two steps: $00111....111 \rightarrow 0100..001111....111$ ($k-1$ zeroes right of that first one) and then into $111....11111$ and we're done. Now assume $k=\frac{n-1}{2}$ (we needed to check this since it might screw up the induction). Order the bits $000....001111....111$ ($n$ odd bits). Now flip the first $k$ bits, then flip $k$ bits but starting from the second position. With this algorithm we have an increase in the zeroes steadily (for large enough $n$) thus at one point we'll have exactly $k$ zeroes/ones and flip those and we're done.