, 2025

Combinatorics Difficulty 8.9 Shortlist Prove it China

For a finite non-empty set $A$ of real numbers, let $\max(A)$ denote its maximum element, and define:
$P(A) = \sum_{\substack{B \subseteq A \\ |B| \text{ odd}}} m(B), \quad Q(A) = \sum_{\substack{\emptyset \neq B \subseteq A \\ |B| \text{ even}}} m(B),$
where $m(B)$ is the median of finite non-empty set $B$ : if $B = \{b_1, b_2, \dots, b_n\}$ ( $b_1 < b_2 < \dots < b_n$ ), then $m(B) = \frac{1}{2}(b_{\lfloor \frac{n+1}{2} \rfloor} + b_{\lceil \frac{n+1}{2} \rceil})$ .
Find the smallest real number $c$ such that for any set $A$ of 2025 distinct positive real numbers,
$P(A) - Q(A) \leq c \cdot \max(A).$

Solution

Without loss of generality, let the elements of $A$ in increasing order be $x_0, x_1, \dots, x_{2024}$ . We first compute $P(A)$ . For each $x_m$ , we count how many odd-sized subsets have $x_m$ as their median. A subset $B$ of odd size has $x_m$ as its median if and only if
$|B \cap \{x_0, \dots, x_{m-1}\}| = |B \cap \{x_{m+1}, \dots, x_{2024}\}|.$
If this common value is $d$ , the number of such subsets $B$ is $\binom{m}{d}\binom{2024-m}{d}$ . Thus, the total number of such $B$ is
$\sum_d \binom{m}{d} \binom{2024-m}{d} = \sum_d \binom{m}{m-d} \binom{2024-m}{d} = \binom{2024}{m},$
where the last equality follows from Vandermonde's identity. Therefore,
$P = \sum_{m=0}^{2024} \binom{2024}{m} x_m.$
Next, we compute $Q(A)$ . For each $x_m$ , we count how many even-sized subsets have $x_m$ as one of their two middle elements. The number of such subsets is
$\begin{aligned} & \sum_d \left( \binom{m}{d+1} \binom{2024-m}{d} + \binom{m}{d} \binom{2024-m}{d+1} \right) \\ &= \sum_d \binom{m}{m-d-1} \binom{2024-m}{d} + \sum_d \binom{m}{m-d} \binom{2024-m}{d+1} \\ &= \binom{2024}{m-1} + \binom{2024}{m+1}. \end{aligned}$
Thus,
$Q = \sum_{m=0}^{2024} \frac{1}{2} \left( \binom{2024}{m-1} + \binom{2024}{m+1} \right) x_m.$

---

Since multiplying all elements of $A$ by a positive constant does not change the problem, we may assume $x_{2024} = 1$ . Let $y_i = x_i - x_{i-1}$ for $i = 0, 1, \dots, 2024$ (with $x_{-1} = 0$ ). Then $P-Q$ can be expressed as a linear form in $y_0, y_1, \dots, y_{2024}$ , where the $y_i$ are positive and sum to 1. The minimal $c$ is therefore equal to the maximum coefficient of the $y_i$ .
The coefficient of $x_m$ in $P-Q$ is $\binom{2024}{m} - \frac{1}{2}(\binom{2024}{m-1} + \binom{2024}{m+1})$ . Thus, the coefficient of $y_i$ is
$\begin{aligned} & \sum_{m=i}^{2024} \left( \binom{2024}{m} - \frac{1}{2} \left( \binom{2024}{m-1} + \binom{2024}{m+1} \right) \right) \\ &= \sum_{m=i}^{2024} \binom{2024}{m} - \frac{1}{2} \left( \sum_{m=i-1}^{2024} \binom{2024}{m} + \sum_{m=i+1}^{2024} \binom{2024}{m} - 1 \right) \\ &= \frac{\binom{2024}{i} - \binom{2024}{i-1} + 1}{2}. \end{aligned}$
We now find the maximum of $\binom{2024}{i} - \binom{2024}{i-1}$ . For $i \ge 1013$ , $\binom{2024}{i} - \binom{2024}{i-1} \le 0$ , so the maximum must occur for $0 \le i \le 1012$ . Let $d_i = \binom{2024}{i} - \binom{2024}{i-1}$ . Then
$\begin{aligned} d_{i+1} - d_i &= \binom{2024}{i+1} + \binom{2024}{i-1} - 2\binom{2024}{i} \\ &= \binom{2024}{i} \left( \frac{2025-i}{i+1} + \frac{i}{2025-i} - 2 \right) \\ &= \binom{2024}{i} \left( \frac{2025 \times 2026}{(i+1)(2025-i)} - 4 \right). \end{aligned}$
For $0 \le i \le 1010$ , $(i+1)(2025-i)$ increases with $i$ . Since $\frac{2025 \times 2026}{991 \times 1035} < 4 < \frac{2025 \times 2026}{990 \times 1036}$ , we have $d_{i+1} > d_i$ when $i \le 989$ and $d_{i+1} < d_i$ when $i \ge 990$ . Thus, the maximum of $d_i$ is achieved at $i = 990$ . Therefore, the minimal $c$ is
$c = \frac{\binom{2024}{990} - \binom{2024}{989} + 1}{2}.$

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.