CombinatoricsDifficulty 4.6AIMEProve itSoviet Union
Problem:
The finite sequence {an} has each member 0, 1 or 2. A move involves replacing any two unequal members of the sequence by a single member different from either. A series of moves results in a single number. Prove that no series of moves can terminate in a (single) different number.
Solution
Solution:
Suppose we start with a0s, b1s and c2s. Each move changes the parity of all of a, b, c. Each move reduces the length of the sequence by 1, so there must be a+b+c−1 moves in all. Hence the total number of 0s, the total number of 1s and the total number of 2s all have their parity changed a+b+c−1 times. So if we end up with just one 0, then a must have the opposite parity to b and c. In that case, we cannot end up with just one 1, or just one 2. Similarly in the other cases.
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.