Number theoryDifficulty 5.8AIME, harderProve itIndia
Problem: From a set of 11 square integers, show that one can choose 6 numbers a2,b2,c2,d2,e2,f2 such that a2+b2+c2≡d2+e2+f2(mod12)
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 numbers
Even numbers
Odd pairs
Even pairs
Total pairs
0
11
0
5
5
1
10
0
5
5
2
9
1
4
5
3
8
1
4
5
4
7
2
3
5
5
6
2
3
5
6
5
3
2
5
7
4
3
2
5
8
3
4
1
5
9
2
4
1
5
10
1
5
0
5
11
0
5
0
5
Let us take such 5 pairs: say (x12,y12),(x22,y22),…,(x52,y52). Then xj2−yj2 is divisible by 4 for 1≤j≤5. Let rj be the remainder when xj2−yj2 is divisible by 3,1≤j≤5. We have 5 remainders r1,r2,r3,r4,r5. 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=r3, then 3 divides r1+r2+r3; if r1=0,r2=1 and r3=2, then again 3 divides r1+r2+r3. 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) such that 3 divides (x12−y12)+(x22−y22)+(x32−y32). Since each difference is divisible by 4, we conclude that we can find 6 numbers a2,b2,c2,d2,e2,f2 such that a2+b2+c2≡d2+e2+f2(mod12)
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.