Competition problem — Combinatorics

Library / /23 of 23

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

A gadget has four dials in a row, each of which can be turned to point to one of three numbers: $0$ (left), $1$ (up) or $2$ (right). Initially the dials are in the respective positions $2,0,1,0$ , so that the gadget reads "2010." You may perform the following operation: choose two adjacent dials pointing at different numbers, and turn them to point to the third number. For example, taking the first two dials, you could change "2010" to "1110." Is it possible to perform a sequence of such operations so that the gadget reads "2011"?

Solution

Solution:

The answer is no. We notice that initially the sum of the numbers on the dials is $3$ . We claim that after each operation, the sum of the numbers on the dials remains a multiple of $3$ . To see this, consider the three possible types of moves:
(a) Changing a $0$ and a $2$ to two $1$ 's does not change the digit sum.
(b) Changing a $0$ and a $1$ to two $2$ 's increases the sum by $3$ .
(c) Changing a $1$ and a $2$ to two $0$ 's decreases the sum by $3$ .
Thus, the sum always goes up or down by multiples of $3$ , and thus we cannot reach the position $2011$ in which the sum is $4$ .

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.