Browse · MathNet
Print62nd Ukrainian National Mathematical Olympiad
Ukraine counting and probability
Problem
There are children standing in a circle, each of them has two cards, one with the digit and the other with the digit . At a certain moment, each child raises one of their cards at their discretion. Then every minute, each child whose card number is different from the numbers on both of their neighbors' cards (on the left and on the right) changes their card. Can the situation last indefinitely, when at least one child changes their card?
Solution
For even , at the beginning, the kids flip every other sign, starting with and . Then, every minute, they continue to flip the signs alternately, and this will go on forever.
For odd , such a distribution is not possible. If two identical digits are next to each other, they will remain so forever. Such signs are called stable. All unstable signs change every minute. Let's consider any group of stable digits that are next to each other. We also consider the group of unstable signs that are next to the stable group. It consists of digits that alternate: (or in a different order). Such a group is adjacent to a stable group on each side, and therefore loses two end elements that are added to the stable group. Thus, all unstable groups will disappear after some time, and the process will stop.
For odd , such a distribution is not possible. If two identical digits are next to each other, they will remain so forever. Such signs are called stable. All unstable signs change every minute. Let's consider any group of stable digits that are next to each other. We also consider the group of unstable signs that are next to the stable group. It consists of digits that alternate: (or in a different order). Such a group is adjacent to a stable group on each side, and therefore loses two end elements that are added to the stable group. Thus, all unstable groups will disappear after some time, and the process will stop.
Final answer
Yes, if the number of children is even (an alternating arrangement yields perpetual flipping); no, if the number is odd (the process eventually stops).
Techniques
Invariants / monovariants