Maths Olympiad Prep

Track / Stage 7 / 89 of 300 #1489 of 1964

Problem 1489

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Prove it

Let n0n \ne 0 be a natural number and integers x1,x2,....,xn,y1,y2,....,ynx_1, x_2, ...., x_n, y_1, y_2, ...., y_n with the properties:
a) x1+x2+....+xn=y1+y2+....+yn=0,x_1 + x_2 + .... + x_n = y_1 + y_2 + .... + y_n = 0,
b) x12+y12=x22+y22=....=xn2+yn2x_1 ^ 2 + y_1 ^ 2 = x_2 ^ 2 + y_2 ^ 2 = .... = x_n ^ 2 + y_n ^ 2.
Show that nn is even.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. **Assume n n is odd.** Let xi2+yi2=k x_i^2 + y_i^2 = k for all i i . From the given conditions, we have:
i=1nxi=i=1nyi=0 \sum_{i=1}^n x_i = \sum_{i=1}^n y_i = 0
and
x12+y12=x22+y22==xn2+yn2=k. x_1^2 + y_1^2 = x_2^2 + y_2^2 = \cdots = x_n^2 + y_n^2 = k.

2. Consider the congruence modulo 2. Note that z2z(mod2) z^2 \equiv z \pmod{2} for any integer z z . Therefore, summing the squares, we get:
i=1nxi2+i=1nyi2=kni=1nxi+i=1nyi=00(mod2). \sum_{i=1}^n x_i^2 + \sum_{i=1}^n y_i^2 = k \cdot n \equiv \sum_{i=1}^n x_i + \sum_{i=1}^n y_i = 0 \equiv 0 \pmod{2}.
This implies:
kn0(mod2). k \cdot n \equiv 0 \pmod{2}.

3. **Since n n is odd, k k must be even.** This is because the product of an odd number and an even number is even. Therefore, k0(mod2) k \equiv 0 \pmod{2} .

4. **Analyze the parity of xi x_i and yi y_i .** Since xi2+yi2=k0(mod2) x_i^2 + y_i^2 = k \equiv 0 \pmod{2} , both xi x_i and yi y_i must have the same parity (either both are even or both are odd). Assume there exist xi x_i and xj x_j of different parity. Then:
k=xi2+yi20(mod4) k = x_i^2 + y_i^2 \equiv 0 \pmod{4}
but also
k=xj2+yj22(mod4), k = x_j^2 + y_j^2 \equiv 2 \pmod{4},
which is a contradiction. Hence, all xi x_i and yi y_i must have the same parity.

5. **Consider the case where all xi x_i and yi y_i are odd.** From condition (a), the sum of n n odd numbers must be even, which implies n n must be even. This contradicts our assumption that n n is odd.

6. **Consider the case where all xi x_i and yi y_i are even.** Let xi=2αiai x_i = 2^{\alpha_i} \cdot a_i and yi=2βibi y_i = 2^{\beta_i} \cdot b_i , where ai a_i and bi b_i are odd. Without loss of generality, assume x1 x_1 has the lowest power of 2 fully dividing it. From x12+y12=k x_1^2 + y_1^2 = k , we get:
22α1k. 2^{2\alpha_1} \mid k.
Let k=22α1r k = 2^{2\alpha_1} \cdot r . Then:
a12+22β12α1b12=r. a_1^2 + 2^{2\beta_1 - 2\alpha_1} b_1^2 = r.
Since a1 a_1 is odd, we have two cases:
1. β1=α1 \beta_1 = \alpha_1 .
2. r r is odd, and thus 22α1 2^{2\alpha_1} fully divides k k .

Both cases lead to a contradiction if n n is odd.

Therefore, n n must be even.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.