Maths Olympiad Prep

Library / /16 of 65

Combinatorics Difficulty 5.5 AIME, harder Prove it Bulgaria

Problem:

Let nn be a positive integer. Ann writes down nn different positive integers. Then Ivo deletes some of them (possibly none, but not all), puts the signs ++ or - in front of each of the remaining numbers and sums them up. Ivo wins if 20032003 divides the result; otherwise, Ann wins. Who has a winning strategy?

Solution

Solution:

For n10n \leq 10 Ann wins by writing the numbers 1,2,,2n11, 2, \ldots, 2^{n-1}. Indeed, the result Ivo can get is a non-zero integer between 1023-1023 and 10231023, since it has the same sign as the largest remaining number (2j>2j1=i=0j12i)\left(2^{j} > 2^{j}-1 = \sum_{i=0}^{j-1} 2^{i}\right).

For n11n \geq 11 the set CC of Ann's numbers has 2n1>20032^{n}-1 > 2003 different nonempty subsets. Hence the sums of numbers of two of them, say AA and BB, are congruent modulo 20032003. If Ivo puts ++ in front of the numbers of ABA \setminus B, - in front of the numbers of BAB \setminus A and deletes the remaining numbers of CC, he wins.

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.