InterviewSolution
| 1. |
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 (mod 12). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Answer» 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:
Let us take such 5 pairs: say (x21 ; y21); (x22 ; y22); .... (x25 ; y25). Then x2j - y2j is divisible by 4 for 1 ≤ j ≤ 5. Let rj be the remainder when x2j - y2j is divisible by 3, 1 ≤ j ≤ 3. We have 5 remainders r1; r2; r3; r4; r5. But these can be 0, 1 or 2. Hence either one of the remainders occur 3 times or each of the remainders occur 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, (x21 ; y21); (x22 ; y22); (x23 ; y23) such that 3 divides (x21 - y21) + (x22 - y22)+(x23 - y23). 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 (mod 12): |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||