Maths Olympiad Prep

Library / /10 of 10

Combinatorics Difficulty 9.2 IMO level Prove it China

There are 20252025 people and 6666 given colors. Each person has 6666 balls, one of each color, with a total weight of 11 for all 6666 balls.
Find the smallest real number CC such that, no matter how the balls are weighted, one can always select exactly one ball from each person so that for every color, the total weight of the selected balls of that color does not exceed CC.

Solution

Let's generalize the problem by replacing 20252025 with nn and 6666 with mm. For any positive integers mnm \le n, define:
fm(n)=mina1+a2++am=na1,a2,,am are positive integers(1a1+1a2++1am). f_m(n) = \min_{\substack{a_1+a_2+\dots+a_m=n \\ a_1, a_2, \dots, a_m \text{ are positive integers}}} \left( \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_m} \right).

We prove the lemma by induction on mm. For m=1m=1, fm(n+m1)=f1(n)=1nf_m(n+m-1) = f_1(n) = \frac{1}{n}, and the statement holds. Assume the statement holds for m1m-1, and consider the case with mm colors.
For i=1,2,,ni = 1, 2, \dots, n, let xix_i be the weight of the first color ball for person PiP_i, and assume without loss of generality that x1x2xnx_1 \le x_2 \le \dots \le x_n. Choose non-negative integer kk such that
x1+x2++xkA,x1+x2++xk+xk+1>A. x_1 + x_2 + \dots + x_k \le A, \quad x_1 + x_2 + \dots + x_k + x_{k+1} > A.
Then xk+1x1++xk+1k+1>Ak+1x_{k+1} \ge \frac{x_1+\dots+x_{k+1}}{k+1} > \frac{A}{k+1}. Therefore, for people Pk+1,Pk+2,,PnP_{k+1}, P_{k+2}, \dots, P_n (nkn-k people), the total weight of their m1m-1 balls (colors 2,3,,m2, 3, \dots, m) is at most
fm(n+m1)AAk+1fm1(nk+m2)A. f_m(n+m-1) \cdot A - \frac{A}{k+1} \le f_{m-1}(n-k+m-2) \cdot A.
This inequality holds because
minb1++bm1=nk+m2(1b1++1bm1)+1k+1mina1++am=n+m1(1a1++1am). \min_{b_1+\cdots+b_{m-1}=n-k+m-2} \left( \frac{1}{b_1} + \cdots + \frac{1}{b_{m-1}} \right) + \frac{1}{k+1} \ge \min_{a_1+\cdots+a_m=n+m-1} \left( \frac{1}{a_1} + \cdots + \frac{1}{a_m} \right).
By the induction hypothesis, we can select one ball (from colors 2,3,,m2, 3, \dots, m) from each of Pk+1,Pk+2,,PnP_{k+1}, P_{k+2}, \dots, P_n such that the total weight of each color among the selected balls is at most AA. This completes the induction.

Substituting A=1fm(n+m1)A = \frac{1}{f_m(n+m-1)} in the lemma, we see that C=1fm(n+m1)C = \frac{1}{f_m(n+m-1)} satisfies the requirement.
Suppose fm(n+m1)=1a1++1am where a1++am=n+m1. \text{Suppose } f_m(n+m-1) = \frac{1}{a_1} + \cdots + \frac{1}{a_m} \text{ where } a_1 + \cdots + a_m = n+m-1.

If C<1fm(n+m1)C < \frac{1}{f_m(n+m-1)}, consider the following scenario: For each person, the weight of their kk-th color ball is
1ak×11a1++1am(>1ak×C), \frac{1}{a_k} \times \frac{1}{\frac{1}{a_1} + \dots + \frac{1}{a_m}} \left( > \frac{1}{a_k} \times C \right),
and the total weight of each person's mm balls is 11. In this case, the number of selected balls of color kk is at most ak1a_k - 1, so the total number of selected balls would be at most (a11)++(am1)=n1(a_1 - 1) + \dots + (a_m - 1) = n - 1, which is a contradiction.
Therefore, the minimal CC is Cmin=1fm(n+m1)C_{\min} = \frac{1}{f_m(n+m-1)}.
Let n=mq+rn = mq + r where 1rm1 \le r \le m, i.e., n+m1=m(q+1)+(r1)=(r1)(q+2)+(m+1r)(q+1)n + m - 1 = m(q + 1) + (r - 1) = (r-1)(q+2) + (m+1-r)(q+1). Since 1x\frac{1}{x} is convex, the sum 1a1++1am\frac{1}{a_1} + \dots + \frac{1}{a_m} is minimized when a1,,ama_1, \dots, a_m consist of (r1)(r-1) copies of (q+2)(q+2) and (m+1r)(m+1-r) copies of (q+1)(q+1). Thus,
Cmin=1fm(n+m1)=1r1q+2+m+1rq+1. C_{\min} = \frac{1}{f_m(n + m - 1)} = \frac{1}{\frac{r-1}{q+2} + \frac{m+1-r}{q+1}}.
In particular, when n=2025n = 2025 and m=66m = 66, the required CC is 248517\frac{248}{517}.
\square

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.