Library / /51 of 69

, 2011

Combinatorics Difficulty 6.0 AIME, harder Prove it South Africa

There are $10$ numbers written around the circumference of a circle. Some of them are positive and others are negative. During one move we are allowed to change the sign of the numbers in three successive positions, each of the three numbers changes sign. Prove that we can make all the numbers positive after a finite number of moves.

Solution

Label the numbers $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ in a clockwise direction around the circle. Notice that if we switch a certain value twice, it remains in its original state. If we switch an element an odd number of times we change its sign. To solve this problem it will suffice to show that we can switch one number's sign and leave all the remaining numbers as they were after a finite number of moves. Without loss of generality, we shall show that the number labelled $0$ can be switched and the remaining numbers left unchanged. If we switch $(9, 0, 1)$ , $(0, 1, 2)$ , $(8, 9, 0)$ , $(2, 3, 4)$ , $(8, 7, 6)$ , $(7, 6, 5)$ , $(5, 4, 3)$ notice that all positions are switched twice except $0$ which is switched $3$ times and hence has its sign changed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.