Olympiad Maths Prep

Library / /1 of 21

, 2007

Number theory Difficulty 7.6 National olympiad, round 2 Prove it IMO

Let XX be a set of 1000010000 integers, none of them is divisible by 4747. Prove that there exists a 20072007-element subset YY of XX such that ab+cd+ea-b+c-d+e is not divisible by 4747 for any a,b,c,d,eYa, b, c, d, e \in Y.

Solution

Call a set MM of integers good if 47ab+cd+e47 \nmid a-b+c-d+e for any a,b,c,d,eMa, b, c, d, e \in M.

Consider the set J={9,7,5,3,1,1,3,5,7,9}J=\{-9,-7,-5,-3,-1,1,3,5,7,9\}. We claim that JJ is good. Actually, for any a,b,c,d,eJa, b, c, d, e \in J the number ab+cd+ea-b+c-d+e is odd and
45=(9)9+(9)9+(9)ab+cd+e9(9)+9(9)+9=45. -45 = (-9) - 9 + (-9) - 9 + (-9) \leq a-b+c-d+e \leq 9 - (-9) + 9 - (-9) + 9 = 45.
But there is no odd number divisible by 4747 between 45-45 and 4545.

For any k=1,,46k = 1, \ldots, 46 consider the set
Ak={xXjJ:kxj(mod47)}. A_{k} = \{x \in X \mid \exists j \in J: \quad kx \equiv j \pmod{47}\}.
If AkA_{k} is not good, then 47ab+cd+e47 \mid a-b+c-d+e for some a,b,c,d,eAka, b, c, d, e \in A_{k}, hence 47kakb+kckd+ke47 \mid k a - k b + k c - k d + k e. But set JJ contains numbers with the same residues modulo 4747, so JJ also is not good. This is a contradiction; therefore each AkA_{k} is a good subset of XX.

Then it suffices to prove that there exists a number kk such that Ak2007|A_{k}| \geq 2007. Note that each xXx \in X is contained in exactly 1010 sets AkA_{k}. Then
k=146Ak=10X=100000 \sum_{k=1}^{46} |A_{k}| = 10|X| = 100000
hence for some value of kk we have
Ak10000046>2173>2007 |A_{k}| \geq \frac{100000}{46} > 2173 > 2007

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.