Competition problem — Combinatorics

Library / /17 of 22

Combinatorics Difficulty 5.4 AIME, harder Prove it United States

Problem:

The number $2011$ is written on a blackboard. It is permitted to transform the numbers on it by two types of moves:

a) Given a number $n$ , we can erase $n$ and write two nonnegative integers $a$ and $b$ such that $a+b=n$ .

b) Given two numbers $a$ and $b$ , we can erase them and write their difference $a-b$ , assuming this is positive or $0$ .

Is it possible that after a sequence of such moves, there is only one number on the blackboard and it is $0$ ?

Solution

Solution:

The answer is no.

We claim that the sum of the numbers on the blackboard is always odd. Indeed, the initial sum, $2011$ , is odd, and when a move of type (a) is performed, the sum does not change. When a move of type (b) is performed, the sum decreases by
$(a+b)-(a-b)=2b,$
an even number. Since odd $-$ even $=$ odd, the sum will remain odd. Thus the desired final state, in which the sum ( $0$ ) is even, is not achievable.

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.