Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /245 of 359

Taiwan IMO Selection Camp, 2023

Algebra Difficulty 6.3 National Olympiad Prove it Taiwan

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

Note: The tt-th power mean of positive real numbers x1,…,xnx_1, \dots, x_n is defined as
(x1t+⋯+xntn)1t(if t≠0);x1⋯xnn(if t=0).Foreverypositiveinteger$k$greaterthan1,findthelargestrealnumber$t$suchthatthefollowinghold:Given$n$distinctpoints$a(1)=(a1(1),⋯ ,ak(1))$,$⋯$,$a(n)=(a1(n),⋯ ,ak(n))$in$Rk$,wedefinethescoreofthetuple$a(i)$as \left( \frac{x_1^t + \dots + x_n^t}{n} \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
∏j=1k#{1≤\prod_{j=1}^{k} \#\{1 \le i' ≤n\le n \text{} such that } πj(a(i′))=πj(a(i))}\pi_j(a^{(i')}) = \pi_j(a^{(i)})\}
where$#S$isthenumberofelementsinset$S$,and$πj$istheprojection$Rk→Rk−1$omittingthe$j$−thcoordinate.Thenthe$t$−thpowermeanofthescoresofall$a(i)$′sisatmost$n$.Note:The$t$−thpowermeanofpositiverealnumbers$x1,⋯ ,xn$isdefinedas 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
( x 1 t +\text{( x 1 t +} + x_n^t}{n} )1t\left. \right)^{\frac{1}{t}}

Solution

The answer is 1k−1\frac{1}{k-1}. To see that t≤1k−1t \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,…,m1, 2, \dots, m. Then n=km+1n = km + 1 and the score of the zero sequence is mkm^k. In order for the statement to hold, we must have
(mktkm+1)1t≤km+1, \left( \frac{m^{kt}}{km + 1} \right)^{\frac{1}{t}} \le km + 1,
i.e., mk≤(km+1)1+1/tm^k \le (km + 1)^{1+1/t}. By choosing mm to be sufficiently large, we get
k≤1+1t, or t≤1k−1. k \le 1 + \frac{1}{t}, \text{ or } t \le \frac{1}{k-1}.

Now we will prove by induction on kk that t=1k−1t = \frac{1}{k-1} works. We first assume that k≥3k \ge 3 and the statement holds for k−1k-1. For every real number rr, let crc_r be the number of sequences a(i)a^{(i)} with a1(i)=ra_1^{(i)} = r. For each rr with cr≠0c_r \ne 0, we gather the sequences with a1(i)=ra_1^{(i)} = r and compute their scores when we remove the first component. Let the scores be s1′,⋯ ,scr′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 d1,⋯ ,dcrd_1, \cdots, d_{c_r}. Then clearly d1+⋯+dcr≤nd_1 + \cdots + d_{c_r} \le n as all sequences are distinct. Note that the scores of the original sequences we gather are precisely d1s1′,⋯ ,dcrscr′d_1 s'_1, \cdots, d_{c_r} s'_{c_r}. By the inductive hypothesis, we have
s11k−2+⋯+scr1k−2=crk−1k−2. 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
((d1s1′)1k−1+⋯+(dcrscr′)1k−1)k−1≤(d1+⋯+dcr)⋅(s11k−2+⋯+scr1k−2)k−2≤ncrk−1. ((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)(k-1)-th root of both sides and adding it up for all r∈Rr \in \mathbb{R} with cr≠0c_r \ne 0, we get that the 1k−1\frac{1}{k-1}-th power mean is bounded by
(∑cr≠0n1k−1crn)k−1=n \left( \frac{\sum_{c_r \ne 0} n^{\frac{1}{k-1}} c_r}{n} \right)^{k-1} = n
as
∑cr≠0cr=n. \sum_{c_r \ne 0} c_r = n.
For the base case k=2k=2, we can follow the same proof except that we clearly have
s1′=⋯=scr′=n s'_1 = \cdots = s'_{c_r} = n
and so
(d1s1′+⋯+dcrscr′)=n(d1+⋯+dcr)≤n2 (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,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.