Maths Olympiad Prep

Track / Stage 5 / 395 of 400 #995 of 1964

Problem 995

AIME late
Number theory Difficulty 6.0 Prove it

777 \cdot 7 Write the numbers 1,2,3,,19741,2,3, \cdots, 1974 on the blackboard. It is allowed to erase any two numbers and write down their sum or difference, repeating this procedure until only one number remains on the blackboard. Prove that this number cannot be zero.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

[Proof] Consider the number of odd numbers on the blackboard.
After one operation, if it is an odd number and an even number, then by the sum and difference of an odd number and an even number being odd, one odd number and one even number are erased to get one odd number. In this case, the number of odd numbers remains unchanged.

If it is two odd numbers, then by the sum and difference of two odd numbers being even, two odd numbers are erased to get one even number, and similarly, two even numbers are erased to get one even number, in which case, the number of odd numbers decreases by 2 or remains unchanged.
From the above, after the operation, the parity of the number of odd numbers on the blackboard does not change.
Since there are initially 19742=987\frac{1974}{2}=987 odd numbers on the blackboard, i.e., an odd number of odd numbers, after several operations, there must be an odd number of odd numbers left on the blackboard, and thus it cannot be 0.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.