Maths Olympiad Prep

Library / /46 of 121

Number theory Difficulty 5.8 AIME, harder Prove it India

Problem:
From a set of 11 square integers, show that one can choose 6 numbers a2,b2,c2,d2,e2,f2a^{2}, b^{2}, c^{2}, d^{2}, e^{2}, f^{2} such that
a2+b2+c2d2+e2+f2(mod12) a^{2}+b^{2}+c^{2} \equiv d^{2}+e^{2}+f^{2} \quad(\bmod 12)

Solution

Solution:
The first observation is that we can find 5 pairs of squares such that the two numbers in a pair have the same parity. We can see this as follows:

Odd numbersEven numbersOdd pairsEven pairsTotal pairs
011055
110055
29145
38145
47235
56235
65325
74325
83415
92415
101505
110505

Let us take such 5 pairs: say (x12,y12),(x22,y22),,(x52,y52)\left(x_{1}^{2}, y_{1}^{2}\right),\left(x_{2}^{2}, y_{2}^{2}\right), \ldots,\left(x_{5}^{2}, y_{5}^{2}\right). Then xj2yj2x_{j}^{2}-y_{j}^{2} is divisible by 4 for 1j51 \leq j \leq 5. Let rjr_{j} be the remainder when xj2yj2x_{j}^{2}-y_{j}^{2} is divisible by 3,1j53, 1 \leq j \leq 5. We have 5 remainders r1,r2,r3,r4,r5r_{1}, r_{2}, r_{3}, r_{4}, r_{5}. But these can be 0, 1 or 2. Hence either one of the remainders occurs 3 times or each of the remainders occurs once. If, for example, r1=r2=r3r_{1}=r_{2}=r_{3}, then 3 divides r1+r2+r3r_{1}+r_{2}+r_{3}; if r1=0,r2=1r_{1}=0, r_{2}=1 and r3=2r_{3}=2, then again 3 divides r1+r2+r3r_{1}+r_{2}+r_{3}. Thus we can always find three remainders whose sum is divisible by 3. This means we can find 3 pairs, say, (x12,y12),(x22,y22),(x32,y32)\left(x_{1}^{2}, y_{1}^{2}\right),\left(x_{2}^{2}, y_{2}^{2}\right),\left(x_{3}^{2}, y_{3}^{2}\right) such that 3 divides (x12y12)+(x22y22)+(x32y32)\left(x_{1}^{2}-y_{1}^{2}\right)+\left(x_{2}^{2}-y_{2}^{2}\right)+\left(x_{3}^{2}-y_{3}^{2}\right). Since each difference is divisible by 4, we conclude that we can find 6 numbers a2,b2,c2,d2,e2,f2a^{2}, b^{2}, c^{2}, d^{2}, e^{2}, f^{2} such that
a2+b2+c2d2+e2+f2(mod12) a^{2}+b^{2}+c^{2} \equiv d^{2}+e^{2}+f^{2} \quad(\bmod 12)

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.