Maths Olympiad Prep

Track / Stage 6 / 202 of 400 #1202 of 1964

Problem 1202

National olympiad, first round
Algebra Difficulty 6.3 Prove it

Sure, here is the translated text:

```
II. (50 points)
Define \oplus as follows:
(a,b)(c,d)=(a+c,b+d+ac) Define (m,n)(pq)mp,nq.n(a,b)=(a,b)(a,b)(a,b)n timesnN \begin{array}{l} (a, b) \oplus(c, d)=(a+c, b+d+a c) \\ \text { Define }(m, n) \leqslant(p \cdot q) \Leftrightarrow m \leqslant p, n \leqslant q . \\ n(a, b)=\underbrace{(a, b) \oplus(a, b) \oplus \cdots \oplus(a, b)}_{n \text{ times}} n \in N \end{array}

Prove: (a1,b1)(a2,b2)(an,bn)\left(a_{1}, b_{1}\right) \oplus\left(a_{2}, b_{2}\right) \oplus \cdots \oplus\left(a_{n}, b_{n}\right) \leqslant
n(a1++ann,b1++bnn)(n2nN) n\left(\frac{a_{1}+\cdots+a_{n}}{n}, \frac{b_{1}+\cdots+b_{n}}{n}\right)(n \geqslant 2 \quad n \in N)
```

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

 =, {50 points} (a1,b1)(9(a2,b2)=(a1+a2,b1+b2+a1a2) Let (a1,b1)(ak,bk)=(a1+a2++ak,b1+b2++bk+1i<jkaiaj)(k2kN) \begin{array}{l} \text { =, \{50 points\} } \\ \left(a_{1}, b_{1}\right)\left(9\left(a_{2}, b_{2}\right)=\left(a_{1}+a_{2}, b_{1}+b_{2}+a_{1} a_{2}\right)\right. \\ \quad \text { Let }\left(a_{1}, b_{1}\right) \oplus \cdots \oplus\left(a_{k}, b_{k}\right)=\left(a_{1}+a_{2}+\cdots+a_{k}, b_{1}+b_{2}+\cdots+b_{k}\right. \\ \left.+\sum_{1 \leqslant i<j \leqslant k} a_{i} a_{j}\right)(k \geqslant 2 \quad k \in \mathbb{N}) \end{array}

Then (a1,b1)(ak,bk)(ak+1,bk+1)\left(a_{1}, b_{1}\right) \oplus \cdots \oplus\left(a_{k}, b_{k}\right) \oplus\left(a_{k+1}, b_{k+1}\right)
=(a1+a2++ak,b1+b2++bk+1i<jkaiaj)(ak+1,bk+1)=(a1+a2++ak+1,b1+b2++bk+1+1i<jkaiaj+ak+1j=1kaj)=(a1+a2++ak+1,b1+b2++bk+1+1i<jk+1aiaj) \begin{array}{l} =\left(a_{1}+a_{2}+\cdots+a_{k}, b_{1}+b_{2}+\cdots+b_{k}+\sum_{1 \leqslant i<j \leqslant k} a_{i} a_{j}\right) \oplus\left(a_{k+1}, b_{k+1}\right) \\ =\left(a_{1}+a_{2}+\cdots+a_{k+1}, b_{1}+b_{2}+\cdots+b_{k+1}+\sum_{1 \leqslant i<j \leqslant k} a_{i} a_{j}+a_{k+1} \sum_{j=1}^{k} a_{j}\right) \\ =\left(a_{1}+a_{2}+\cdots+a_{k+1}, b_{1}+b_{2}+\cdots+b_{k+1}+\sum_{1 \leqslant i<j \leqslant k+1} a_{i} a_{j}\right) \end{array}

Therefore, for nN,n2\forall n \in \mathbb{N}, n \geqslant 2
(a1,b1)(a2,b2)(an,bn)=(a1+a2++an,b1+b2++bn+1i<jnaiaj) \begin{array}{l} \left(a_{1}, b_{1}\right) \oplus\left(a_{2}, b_{2}\right) \oplus \cdots \oplus\left(a_{n}, b_{n}\right)=\left(a_{1}+a_{2}+\cdots+a_{n}, b_{1}+b_{2}+\cdots+\right. \\ \left.b_{n}+\sum_{1 \leqslant i<j \leqslant n} a_{i} a_{j}\right) \end{array}

Therefore, n(a1++ann,b1++bnn)n\left(\frac{a_{1}+\cdots+a_{n}}{n}, \frac{b_{1}+\cdots+b_{n}}{n}\right)
=(a1+a2++an,b1+b2++bn+n12n(a1+a2++an)2 \begin{array}{l} =\left(a_{1}+a_{2}+\cdots+a_{n}, b_{1}+b_{2}+\cdots+b_{n}+\frac{n-1}{2 n}\left(a_{1}+a_{2}+\cdots+a_{n}\right)^{2}\right. \\ \end{array}

Notice that 21i<jnaiaj=(a1++an)2i=1nai2n1n(a1+a2++an)22 \sum_{1 \leqslant i<j \leqslant n} a_{i} a_{j}=\left(a_{1}+\cdots+a_{n}\right)^{2}-\sum_{i=1}^{n} a_{i}^{2} \leqslant \frac{n-1}{n}\left(a_{1}+a_{2}+\cdots+a_{n}\right)^{2}
Therefore, (a1,b1)(a2,b2)(an,bn)n(a1++ann,b1++bnn)\left(a_{1}, b_{1}\right) \oplus\left(a_{2}, b_{2}\right) \oplus \cdots \oplus\left(a_{n}, b_{n}\right) \leqslant n\left(\frac{a_{1}+\cdots+a_{n}}{n}, \frac{b_{1}+\cdots+b_{n}}{n}\right)

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