Library / /267 of 397

, 2023

Algebra Difficulty 6.3 National Olympiad Prove it Taiwan

Given a positive integer $k > 1$ and $n$ distinct points in $k$ -dimensional coordinates $a^{(1)} = (a_1^{(1)}, \dots, a_k^{(1)})$ , $\dots, a^{(n)} = (a_1^{(n)}, \dots, a_k^{(n)})$ , we define the "score" of $a^{(i)}$ as follows:
$\prod_{j=1}^{k} \#\{i' \mid 1 \le i' \le n \text{ such that } \pi_j(a^{(i')}) = \pi_j(a^{(i)})\},$
where $\#S$ denotes the number of elements in the set $S$ , and $\pi_j : \mathbb{R}^k \to \mathbb{R}^{k-1}$ is the projection map that sends a point in $k$ -dimensional coordinates to the point obtained by deleting its $j$ -th coordinate. Find the largest real number $t$ such that the $t$ -th power mean of the "scores" of all $a^{(i)}$ is $\le n$ .

Note: The $t$ -th power mean of positive real numbers $x_1, \dots, x_n$ is defined as

$\text{( x 1 t +}$ + x_n^t}{n} $\left. \right)^{\frac{1}{t}} \quad (\text{if}$ } t $\neq$ 0); $\quad \sqrt[n]{x_1 \cdots}$ x_n} $\quad (\text{if}$ } t = 0).

For every positive integer $k$ greater than 1, find the largest real number $t$ such that the following hold: Given $n$ distinct points $a^{(1)} = (a_1^{(1)}, \cdots, a_k^{(1)})$ , $\cdots$ , $a^{(n)} = (a_1^{(n)}, \cdots, a_k^{(n)})$ in $\mathbb{R}^k$ , we define the score of the tuple $a^{(i)}$ as
$\prod_{j=1}^{k} \#\{1 \le i' \le n \text{ such that } \pi_j(a^{(i')}) = \pi_j(a^{(i)})\}$
where $\#S$ is the number of elements in set $S$ , and $\pi_j$ is the projection $\mathbb{R}^k \to \mathbb{R}^{k-1}$ omitting the $j$ -th coordinate. Then the $t$ -th power mean of the scores of all $a^{(i)}$ 's is at most $n$ .

Note: The $t$ -th power mean of positive real numbers $x_1, \cdots, x_n$ is defined as
$\left( \frac{x_1^t + \cdots + x_n^t}{n} \right)^{\frac{1}{t}}$

Solution

The answer is $\frac{1}{k-1}$ . To see that $t \le \frac{1}{k-1}$ , consider the sequences where all but one of the components are equal to 1, and the remaining one component is $1, 2, \dots, m$ . Then $n = km + 1$ and the score of the zero sequence is $m^k$ . In order for the statement to hold, we must have
$\left( \frac{m^{kt}}{km + 1} \right)^{\frac{1}{t}} \le km + 1,$
i.e., $m^k \le (km + 1)^{1+1/t}$ . By choosing $m$ to be sufficiently large, we get
$k \le 1 + \frac{1}{t}, \text{ or } t \le \frac{1}{k-1}.$

Now we will prove by induction on $k$ that $t = \frac{1}{k-1}$ works. We first assume that $k \ge 3$ and the statement holds for $k-1$ . For every real number $r$ , let $c_r$ be the number of sequences $a^{(i)}$ with $a_1^{(i)} = r$ . For each $r$ with $c_r \ne 0$ , we gather the sequences with $a_1^{(i)} = r$ and compute their scores when we remove the first component. Let the scores be $s'_1, \cdots, s'_{c_r}$ . Moreover, for each truncated sequence, we see how many sequences from the original list would have produced the same truncated sequence. Let the number of such sequences be $d_1, \cdots, d_{c_r}$ . Then clearly $d_1 + \cdots + d_{c_r} \le n$ as all sequences are distinct. Note that the scores of the original sequences we gather are precisely $d_1 s'_1, \cdots, d_{c_r} s'_{c_r}$ . By the inductive hypothesis, we have
$s_1^{\frac{1}{k-2}} + \cdots + s_{c_r}^{\frac{1}{k-2}} = c_r^{\frac{k-1}{k-2}}.$
By Hölder's inequality, we have
$((d_1 s'_1)^{\frac{1}{k-1}} + \cdots + (d_{c_r} s'_{c_r})^{\frac{1}{k-1}})^{k-1} \le (d_1 + \cdots + d_{c_r}) \cdot \left(s_1^{\frac{1}{k-2}} + \cdots + s_{c_r}^{\frac{1}{k-2}}\right)^{k-2} \le n c_r^{k-1}.$
By taking the $(k-1)$ -th root of both sides and adding it up for all $r \in \mathbb{R}$ with $c_r \ne 0$ , we get that the $\frac{1}{k-1}$ -th power mean is bounded by
$\left( \frac{\sum_{c_r \ne 0} n^{\frac{1}{k-1}} c_r}{n} \right)^{k-1} = n$
as
$\sum_{c_r \ne 0} c_r = n.$
For the base case $k=2$ , we can follow the same proof except that we clearly have
$s'_1 = \cdots = s'_{c_r} = n$
and so
$(d_1 s'_1 + \cdots + d_{c_r} s'_{c_r}) = n(d_1 + \cdots + d_{c_r}) \le n^2$
and the rest of the proof follows verbatim.

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 translated into English from zh; metadata (topic, difficulty) added by this project.