Partition of circumference into $3k$ arcs

228 Views Asked by At

The following problem is from 1982 Russian Mathematical Olympiad. If you go to this link, and scroll down to the section Russian Math Olympiad, then this is Problem 333 in that text-file.

Let $k$ be a positive integer. There are $3k$ points marked on the circumference. They divide the circumference onto $3k$ arcs. Some $k$ of arcs have length 1, other $k$ of them have length 2, the rest $k$ of them have length 3. Prove that some two of the marked points are the ends of one diameter.

I haven't given too much thought into the problem yet (I probably wouldn't get anywhere), but I thought I would share this awesome problem.

Added. Trivial Observation: The length of the circumference is $k+2k+3k=6k$.

1

There are 1 best solutions below

1
On BEST ANSWER

Assume the crontrary and assume $k$ is chosen minimal. One directly checks that then $k\ge 2$ (i.e. the claim holds for $k=1$ where the arrangement is completely determined up to symmetry).

Colour the given $3k$ points green and their antipodes red. Then one readily sees that the red and green points together partition the circumference into $6k$ arcs all of length $1$ (all points are at integer positions on the circumference of length $6k$). Then any two adjacent green points $ \color{green}\bullet \color{green}\bullet $ (i.e. those making one of the $k$ marked arcs of length $1$) are opposite to two adjacent red points, which must be the interior of a length $3$ arc $\color{green}\bullet \color{red}\bullet \color{red}\bullet \color{green}\bullet $. Hence the neighbourhood of the length $1$ look like $\color{red}\bullet \color{green}\bullet \color{green}\bullet \color{red}\bullet $ (especially, length $1$ arcs cannot be juxtaposed). Assume the (right) neighbbour of a length $1$ arc is a length $2$ arc, $ \color{red}\bullet \color{green}\bullet \color{green}\bullet \color{red}\bullet \color{green}\bullet $. Then opposite this we find $ \color{green}\bullet \color{red}\bullet \color{red}\bullet \color{green}\bullet \color{red}\bullet $ and these two patterns do not overlap (because $k\ge2$ and there are at least $12$ coloured points). By removing the inner three dots of each of these two patterns, $$\begin{align}\color{red}\bullet \color{green}\bullet \color{green}\bullet \color{red}\bullet \color{green}\bullet&\quad\mapsto\quad\color{red}\bullet \color{green}\bullet\\ \color{green}\bullet \color{red}\bullet \color{red}\bullet \color{green}\bullet \color{red}\bullet&\quad\mapsto\quad\color{green}\bullet \color{red}\bullet\\ \end{align}$$ we obtain a valid pattern again, but with one arc of each length less. In other words we find an arrangement for the case $k-1$, which contradicts the minimality of $k$.