Maths Olympiad Prep

Library / /44 of 520

Number theory Difficulty 5.3 AIME, harder Prove it

You have 2007 cards. On each card, a positive integer less than 2008 is written. If you take a number (at least 1) of these cards, the sum of the numbers on the cards is not divisible by 2008. Prove that the same number is written on every card.

Solution

Do not. Let the numbers on the cards be n1,,n2007n_{1}, \ldots, n_{2007} where n1n2n_{1} \neq n_{2}. Let

si=n1+n2++ni, s_{i}=n_{1}+n_{2}+\ldots+n_{i},

for i=1,2,,2007i=1,2, \ldots, 2007. We now know that si(mod2008)s_{i} \equiv \equiv(\bmod 2008) for all ii. Suppose that sisjs_{i} \equiv s_{j} (mod2008)(\bmod 2008) with i1i1 means that the non-empty sum sin2=n1+n3+n4++nis_{i}-n_{2}=n_{1}+n_{3}+n_{4}+\ldots+n_{i} is equal to 0 modulo 2008; again a contradiction.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.