Skip to main content
OlympiadHQ

Browse · MathNet

Print

62nd Ukrainian National Mathematical Olympiad, Third Round, Second Tour

Ukraine counting and probability

Problem

There are points on the circle, one of which is painted black, and the other — white. In one move Hedgehog is allowed to do one of the following operations: repaint in the opposite color two consecutive points of the same color; repaint in the opposite colors two points of different colors, between which there is exactly one other point. Will Hedgehog be able to do such operations so that each point changes its color to the opposite (compared to the initial coloring)?
Solution
Let's enumerate the points in clockwise order (starting, for example, from the black one), by . Note that from the very beginning, there was one more black point in the positions with odd numbers than the black points in the positions with even numbers. After the first operation, we either add one black point to each group or subtract one black point from each group, so the difference between even and odd black points remains constant. After the second operation, we do not change the number of black points in both groups, so their difference remains constant. Thus, the number of black points in odd places will always be one more than in even places. But this contradicts the fact that in the desired configuration, points stand in even places and points stand in odd places.
Final answer
No

Techniques

Invariants / monovariants