IMO 1971 SL 15

Origin: USS

Problem

Natural numbers from 1 to 99 (not necessarily distinct) are written on 99 cards. It is given that the sum of the numbers on any subset of cards (including the set of all cards) is not divisible by 100. Show that all the cards contain the same number.

Solution

Assume the opposite. Then one can numerate the cards 1 to 99, with a number ni written on the card i, so that n98 ̸= n99. Denote by xi the remainder of n1 + n2 + \cdot \cdot \cdot + ni upon division by 100, for i = 1, 2, . . . , 99. All xi must be distinct: Indeed, if xi = xj, i < j, then ni+1 + \cdot \cdot \cdot + nj is divisible by 100, which is impossible. Also, no xi can be equal to 0. Thus, the numbers x1, x2, . . . , x99 take exactly the values 1, 2, . . . , 99 in some order. Let x be the remainder of n1 + n2 + \cdot \cdot \cdot + n97 + n99 upon division by 100. It is not zero; hence it must be equal to xk for some k \in{1, 2, . . ., 99}. There are three cases: (i) x = xk, k \leq97. Then nk+1 + nk+2 + \cdot \cdot \cdot + n97 + n99 is divisible by 100, a contradiction; (ii) x = x98. Then n98 = n99, a contradiction; (iii) x = x99. Then n98 is divisible by 100, a contradiction. Therefore, all the cards contain the same number.