Maths Olympiad Prep

Library / /36 of 196

Combinatorics Difficulty 4.6 AIME Prove it Soviet Union

Problem:

The finite sequence {an}\{a_n\} has each member 00, 11 or 22. 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 aa 00s, bb 11s and cc 22s. Each move changes the parity of all of aa, bb, cc. Each move reduces the length of the sequence by 11, so there must be a+b+c1a + b + c - 1 moves in all. Hence the total number of 00s, the total number of 11s and the total number of 22s all have their parity changed a+b+c1a + b + c - 1 times. So if we end up with just one 00, then aa must have the opposite parity to bb and cc. In that case, we cannot end up with just one 11, or just one 22. 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.