Maths Olympiad Prep

Library / /5 of 18

Algebra Difficulty 6.3 National olympiad Prove it China

Let a1,a2,,a2023a_1, a_2, \dots, a_{2023} be nonnegative real numbers such that a1+a2++a2023=100a_1 + a_2 + \dots + a_{2023} = 100. Let NN denote the number of elements in the following set
{(i,j)1ij2023,aiaj1}. \{(i, j) \mid 1 \le i \le j \le 2023, a_i a_j \ge 1\}.
Prove that N5050N \le 5050, and determine the necessary and sufficient condition for N=5050N = 5050.

Solution

Proof. Let SS be the number of pairs (i,j)(i, j) that satisfy the following conditions:
1i<j2023,aiaj1. 1 \le i < j \le 2023, \quad a_i a_j \ge 1.
Let TT be the number of elements among a1,a2,,a2023a_1, a_2, \dots, a_{2023} that are not less than 11. Then
100=a1+a2++a2023T,(3) 100 = a_1 + a_2 + \dots + a_{2023} \ge T, \qquad (3)
10000=(a1+a2++a2023)2=i=12023ai2+21i<j2023aiajT+2S.(4) 10000 = (a_1 + a_2 + \dots + a_{2023})^2 = \sum_{i=1}^{2023} a_i^2 + 2 \sum_{1 \le i < j \le 2023} a_i a_j \ge T + 2S. \quad (4)
Adding the two equations and dividing by 22, we get N=S+T5050N = S + T \le 5050.
If equality holds, then equality in the above equation (2) holds, which means each ai2a_i^2 is either 00 or 11. That is, among a1,a2,,a2023a_1, a_2, \dots, a_{2023}, exactly 100100 are 11s and 19231923 are 00s. This is a necessary and sufficient condition.

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 and solution reproduced as published; topic and difficulty added by this site.