Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /320 of 359

Taiwan IMO Selection Camp, 2021

Algebra Difficulty 6.9 National Olympiad Prove it Taiwan

Let nn be a positive integer. For each 4n4n-tuple of nonnegative real numbers a1,…,a2na_1, \dots, a_{2n}, b1,…,b2nb_1, \dots, b_{2n} that satisfy ∑i=12nai=∑j=12nbj=n\sum_{i=1}^{2n} a_i = \sum_{j=1}^{2n} b_j = n, define the sets
A:={∑j=12naibjaibj+1:i∈{1,…,2n} s.t. ∑j=12naibjaibj+1≠0}, A := \left\{ \sum_{j=1}^{2n} \frac{a_i b_j}{a_i b_j + 1} : i \in \{1, \dots, 2n\} \text{ s.t. } \sum_{j=1}^{2n} \frac{a_i b_j}{a_i b_j + 1} \neq 0 \right\},
and
B:={∑i=12naibjaibj+1:j∈{1,…,2n} s.t. ∑i=12naibjaibj+1≠0}. B := \left\{ \sum_{i=1}^{2n} \frac{a_i b_j}{a_i b_j + 1} : j \in \{1, \dots, 2n\} \text{ s.t. } \sum_{i=1}^{2n} \frac{a_i b_j}{a_i b_j + 1} \neq 0 \right\}.
Let mm be the minimum element of A∪BA \cup B. Determine the maximum value of mm among those derived from all such 4n4n-tuples a1,…,a2n,b1,…,b2na_1, \dots, a_{2n}, b_1, \dots, b_{2n}.

Solution

The maximum is n2\frac{n}{2}. This is achieved when exactly half of aia_i and exactly half of bjb_j are 11, and the others are 00.

To show that this is the maximum possible, WLOG assume that a1,…,asa_1, \dots, a_s and b1,…,btb_1, \dots, b_t are nonzero, and the rest are zero. Then we have a1+⋯+as=b1+⋯+bt=na_1 + \cdots + a_s = b_1 + \cdots + b_t = n and
min⁡(A∪B)≤1max⁡(s,t)∑i=1s∑j=1taibjaibj+1.(∗) \min(A \cup B) \le \frac{1}{\max(s, t)} \sum_{i=1}^{s} \sum_{j=1}^{t} \frac{a_i b_j}{a_i b_j + 1}. \quad (*)
Let k=stk = st and x(i−1)t+j=aibjx_{(i-1)t+j} = a_i b_j for all i=1,…,si = 1, \dots, s and j=1,…,tj = 1, \dots, t. Then x1,…,xk>0x_1, \dots, x_k > 0 and x1+⋯+xk=(a1+⋯+as)(b1+⋯+bt)=n2x_1 + \cdots + x_k = (a_1 + \cdots + a_s)(b_1 + \cdots + b_t) = n^2. Moreover, we have max⁡(s,t)≥k\max(s, t) \ge \sqrt{k}.

Therefore
min⁡(A∪B)≤1k∑i=1kxixi+1.(∗∗) \min(A \cup B) \le \frac{1}{\sqrt{k}} \sum_{i=1}^{k} \frac{x_i}{x_i + 1}. \quad (**)
Note that the function f(x)=xx+1f(x) = \frac{x}{x+1} is concave for x>−1x > -1. Therefore
∑i=1kxixi+1≤k⋅n2kn2k+1=kn2n2+k. \sum_{i=1}^{k} \frac{x_i}{x_i + 1} \le k \cdot \frac{\frac{n^2}{k}}{\frac{n^2}{k} + 1} = \frac{k n^2}{n^2 + k}.
As a consequence,
min⁡(A∪B)≤kn2n2+k≤n2(∗∗∗) \min(A \cup B) \le \frac{\sqrt{k} n^2}{n^2 + k} \le \frac{n}{2} \quad (***)
where the last inequality follows from AM-GM.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.