Maths Olympiad Prep

Track / Stage 6 / 207 of 400 #1207 of 1964

Problem 1207

National olympiad, first round
Number theory Difficulty 6.3 Prove it

Let E={1,2,3,,200},G={a1,a2,a3,E=\{1,2,3, \cdots, 200\}, G=\left\{a_{1}, a_{2}, a_{3}, \cdots\right., a100}E\left.a_{100}\right\} \subset E, and GG has the following two properties:
I) For any 1i<j1001 \leqslant i<j \leqslant 100, it always holds that
ai+aj201; a_{i}+a_{j} \neq 201 ;
II) i=1100ai=10080\sum_{i=1}^{100} a_{i}=10080.

Prove: The number of odd numbers in GG is a multiple of 4, and the sum of the squares of all numbers in GG is a constant.

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

 II. Let αi=2i1,βi=201αi(i=1,2,,100) and Ei={αi,βi}, \begin{array}{lc} \text { II. Let } & \alpha_{i}=2 i-1, \beta_{i}=201-\alpha_{i}(i=1,2, \cdots, 100) \\ \text { and } & E_{i}=\left\{\alpha_{i}, \beta_{i}\right\}, \end{array}

Then when iji \neq j, EiEj=E_{i} \cap E_{j}=\varnothing, and i=1100Ei=E\bigcup_{i=1}^{100} E_{i}=E.
From i) we know that for any 1i1001 \leqslant i \leqslant 100, it cannot be that EiGE_{i} \subset G.
Furthermore, since the number of elements in GG is exactly equal to the number of sets EiE_{i}, which is 100, GG must necessarily contain exactly one element from each EiE_{i}.
Now suppose GG contains kk odd numbers, and for
1i1<i2<<ik100, 1 \leqslant i_{1}<i_{2}<\cdots<i_{k} \leqslant 100,

we have
ait=αit(1tk), a_{i_{t}}=\alpha_{i_{t}}(1 \leqslant t \leqslant k),

Thus, for jii(1tk)\quad j \neq i_{i}(1 \leqslant t \leqslant k), it must be that aj=βja_{j}=\beta_{j}
From ii)
t=1kαit+jitβj=10080 \sum_{t=1}^{k} \alpha_{i t}+\sum_{j \neq i_{t}} \beta_{j}=10080

On the other hand
j=1100βj=2j=1100j=10100 \sum_{j=1}^{100} \beta_{j}=2 \sum_{j=1}^{100} j=10100
Subtracting (1) from (2)
t=1k(βitαii)=20k2012t=1kαii=20t=1kαit=12(k20120) \begin{array}{c} \sum_{t=1}^{k}\left(\beta_{i t}-\alpha_{i_{i}}\right)=20 \\ k \cdot 201-2 \sum_{t=1}^{k} \alpha_{i_{i}}=20 \\ \sum_{t=1}^{k} \alpha_{i t}=\frac{1}{2}(k \cdot 201-20) \end{array}

From (4), we first deduce that kk must be a positive even number. Let k=2kk=2 k^{\prime}, then k=12kαit=k20110\sum_{k=1}^{2 k^{\prime}} \alpha_{i t}=k^{\prime} \cdot 201-10. Noting that the left side of this equation is even, kk^{\prime} must be a positive even number. Let k=2kk^{\prime}=2 \cdot k^{\prime \prime}, then k=4kk=4 k^{\prime \prime}, which proves that the number of odd numbers in GG must be a multiple of 4.
Now we calculate the sum of the squares of the numbers in GG. The following calculation uses (3):
i=1100αi2=t=1kαit2+jitkβj2=j=1100βj2t=1kβii2+t=1kαit2=j=1100(2j)2t=1k(βit+αit)(βitαit)=4j=1100j2201×20=4×100(100+1)(200+1)64020=13534004020=1349380. \begin{aligned} \sum_{i=1}^{100} \alpha_{i}^{2} & =\sum_{t=1}^{k} \alpha_{i_{t}}^{2}+\sum_{j \neq i_{t}}^{k} \beta_{j}^{2} \\ & =\sum_{j=1}^{100} \beta_{j}^{2}-\sum_{t=1}^{k} \beta_{i_{i}}^{2}+\sum_{t=1}^{k} \alpha_{i_{t}}^{2} \\ & =\sum_{j=1}^{100}(2 j)^{2}-\sum_{t=1}^{k}\left(\beta_{i_{t}}+\alpha_{i_{t}}\right)\left(\beta_{i_{t}}-\alpha_{i_{t}}\right) \\ & =4 \sum_{j=1}^{100} j^{2}-201 \times 20 \\ & =4 \times \frac{100(100+1)(200+1)}{6}-4020 \\ & =1353400-4020=1349380 . \end{aligned}

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