Let $n\ge 3$ be a positive integer. Find the largest real number $t_n$ as a function of $n$ such that the inequality \[\max\left(|a_1+a_2|, |a_2+a_3|, \dots ,|a_{n-1}+a_{n}| , |a_n+a_1|\right) \ge t_n \cdot \max(|a_1|,|a_2|, \dots ,|a_n|)\]holds for all real numbers $a_1, a_2, \dots , a_n$ . Proposed by Rohan Goyal and Rijul Saini
Problem
Source: INMO P4
Tags: inequalities, INMO 2025, real number
Scilyse
19.01.2025 15:10
S.Ragnork1729 wrote: Let $n \geq 3$ be a positive integer. Find the largest real number $t_n$ as a function of $n$ such that the inequality \begin{align*}\max(|a_1 + a_2|, |a_2 + a_3|, \dots, |a_{n - 1} + a_n|, |a_n + a_1|) \geq t_n \cdot \max(|a_1|, |a_2|, \dots, |a_n|)\end{align*}holds for all real numbers $a_1$, $a_2$, $\dots$, $a_n$. ftfy
mathscrazy
19.01.2025 15:49
This problem was proposed by Rohan Goyal and Rijul Saini.
Krave37
19.01.2025 18:16
Rijul sir about to type solution
S.Ragnork1729
19.01.2025 18:22
When I was trying this during the contest was to take $n=2k$ then take $(a_1,a_2,a_3,a_4,...,a_{2k-1},a_{2k})=(-1,+1,-1,+1,...,-1,+1)$ then LHS becomes zero , wondering what should $t_n$ become be? @below shi.. !! I should have shown atleast for $n$ being even , $t_n=0$
alexanderhamilton124
19.01.2025 18:33
For n even its 0, for n odd i think it's 1/2t (a friend told me this)
MS_asdfgzxcvb
19.01.2025 18:36
I think t(n) = 0 when n is even, t(n) = 1/(k+1) when n is 2k+1, for even construction is to take alternating signs, for odd n, take a1, a2 = -k*(a1)/(k+1), a3=+(k-1)a1/(k+1), a4 = -(k-2)a1/(k+1),..... ar = (-1)^(r-1) (k+2-r)a1/k+1 till r<=k+1 and then just reverse a(n+2-r) = a(r).
Rg230403
19.01.2025 23:08
Rijul and my problem!
This problem's story is kind of funny as it originated from something that looks very different. Rijul had sent me a problem which was essentially to show that there exists some constant $t_n$ depending on $n$ such that $(a+b)^{2n}+(b+c)^{2n}+(a+c)^{2n}\ge t_n(a^{2n}+b^{2n}+c^{2n})$ for all reals $a,b,c$. We initially came up with a terrible bound for $t_n$ and submitted it as a joke. Later I noticed that the bound is significantly improved if we use the triangle inequality to show \[|a+b|+|a+c|+|b+c|\ge |a+b+a+c-(b+c)|\ge 2|a|\]and similar results for all three terms. This made for a better bound but the best constant was still out of reach because of the additive nature of the terms on both sides. Then it was noticed that replacing the sum on both sides with a simple max makes the best bound provable!
Thus, the new statement was to find the best $t_n$ such that \[\max(|a+b|, |a+c|, |b+c|)^{2n}\ge t_n \max(|a|,|b|,|c|)^{2n}.\]Here clearly the exponents don't make the statement any more interesting so we decided to just drop that and generalize. Thus, we ended up with the final statement which appeared in the contest. Here's our solution (my writeup so errors are mine):
For the case when $n$ is even, the sequence $a_i=(-1)^i$ implies that $t_n=0$. Now, more interesting when $n$ is odd:
\[\sum_{i=1}^n|a_i+a_{i+1}|\ge |\sum_{i=1}^n (-1)^i (a_i+a_{i+1})|=2|a_1|\]
The same could have been done with $a_2$ or $a_3$ or so on. Thus, \[n\max(|a_1+a_2|,\ldots, |a_n+a_1|)\ge \sum_{i=1}^n|a_i+a_{i+1}|\ge 2\max(|a_1|,\ldots, |a_n|)\implies t_n \ge \frac{2}{n}.\]
Now, the equality case is directly motivated from the triangle inequality. Let $a_n$ be the largest. For simplicity, we just let it be $n$ so that RHS is just $2n$. Now, each of the $a_i+a_{i+1}$ must add up to $2$ or $-2$ for the bound to be tight. This gives us the construction, $a_i=(-1)^i(n-2i)$ which indeed attains the desired bound.
Siddharthmaybe
20.01.2025 00:53
Rijul and Rohan sir cooked to say the least, Nice problem, truly nice for someone with ineqphobia
HogRIDA
20.01.2025 04:28
Reading these stories makes me feel a little less bad about my poor performance as I am reminded that I gave inmo for fun
Scilyse
20.01.2025 16:05
reminds me of my failed attempts at 2023 a5
S_14159
22.01.2025 01:16
Easier than other problems of this year (same as official solution) For $n$ even the trivial sequence $a_{i}=(-1)^{i}k$ works and gives us $t_{n}(a_{i})\leq 0\implies t_{n}=0$. For $n$ odd and $i\in \{1,\dotsc, n\}$ \begin{align*}n\cdot \max\left(|a_{i}+a_{i+1}| , |a_n+a_1|\right)&\geq |a_{1}+a_{n}|+\sum_{i=1}^{n-1}|a_{i}+a_{i+1}|\\&\geq 2\max\left(|a_{i}|\right)\implies t_{n}\geq \frac{2}{n} \end{align*}Note: The equality case will be done by letting $a_{i}+a_{i+1}=\pm 2$
HogRIDA
22.01.2025 04:55
@above I am blanking out a little, could you explain why sum |a(i)+a(i+1)|>=2max(|ai|)
S_14159
22.01.2025 07:45
@above does this help? Take $a_i$ to be the maximum and by triangle inequality we will get an alternating sum \[n\cdot \max\left(|a_1+a_2|, |a_2+a_3|, \dots ,|a_{n-1}+a_{n}| , |a_n+a_1|\right) \geq \left|(a_{i}+a_{i+1})-(a_{i+1}+a_{i+2})+\;\dotsc(a_{n}+1)\dotsc \;+(a_{i-1}+a_{i})\right|\]Things cancel out on RHS and u get $2|a_{i}|$
Euler365
23.01.2025 02:34
For \( n \) odd, note that the answer to the problem is precisely \( \frac{1}{\|A^{-1}\|_\infty} \), where \( A \) is the \( n \times n \) matrix given by: \[ A = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 0 & 0 & \cdots & 1 \end{pmatrix} \]Now each entry of \( A^{-1} \) is either \( \frac{1}{2} \) or \( -\frac{1}{2} \). It follows that the the matrix \( \ell^\infty \)-norm of \( A^{-1} \) ie the maximum of the absolute row sums of \( A^{-1} \) is \( \frac{n}{2} \), which gives us the answer \( \frac{2}{n} \).
Rg230403
23.01.2025 16:26
Euler365 wrote: For \( n \) odd, note that the answer to the problem is precisely \( \frac{1}{\|A^{-1}\|_\infty} \), where \( A \) is the \( n \times n \) matrix given by: \[ A = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 0 & 0 & \cdots & 1 \end{pmatrix} \]Now each entry of \( A^{-1} \) is either \( \frac{1}{2} \) or \( -\frac{1}{2} \). It follows that the the matrix \( \ell^\infty \)-norm of \( A^{-1} \) ie the maximum of the absolute row sums of \( A^{-1} \) is \( \frac{n}{2} \), which gives us the answer \( \frac{2}{n} \). Indeed! A simpler way to state this argument somewhat equivalently for students unfamiliar with the notation is as follows: Let $x_i = a_i + a_{i+1}$. Now, observe that \[a_i = \frac{\sum_{j=0}^{n-1} (-1)^jx_{i+j}}{2}\]and we can choose $x_i$ to be whatever we want. Thus, now if we fix $\max |x_i| =1$ then we want to maximize $\max |a_i|$ as a result. Now, from the equation written, clearly $|a_i|\le \frac{n}{2}$ and equality is achieved by picking $x_i=(-1)^i$. The key observation is indeed just $(a_1,\ldots a_n)\mapsto (a_1+a_2,\ldots, a_n+a_1)$ is an invertible map and then it's just a matter of writing out the inverse.
Manteca
24.01.2025 21:58
Supose $n$ is odd, by dividing every number by $\max(|a_i|)$ and changing the sign under the absolute value, we can assume $a_1 = 1$ and $|a_i| \leq 1$ for every other $a_i$. Note now that $a_2$ and $a_n$ needs to not be positive to secure $LHS \leq 1$ so: $$|a_1 + a_2| = 1 - |a_2|$$$$|a_n + a_1| = - |a_n| + 1$$Now because $n$ is odd there is some index $2 \leq j \leq n-1$ such that both $a_j$ and $a_{j+1}$ have the same sign so: $$|a_j + a_{j+1}| = |a_j| + |a_{j+1}|$$And by triangle inequality: $$\sum_{i = 1}^n |a_i + a_{i+1}| \geq 1 - |a_2| + (\sum_{i = 2}^{j-1} |a_i| - |a_{i+1}|) + |a_j| + |a_{j+1}| + (\sum_{i = j+1}^{n-1} |a_{i+1}| - |a_i|) - |a_n| + 1 = 2$$So: $$n \cdot \max(|a_i + a_{i+1}|) \geq \sum_{i = 1}^n |a_i + a_{i+1}| \geq 2 \Rightarrow t_n \geq \frac{2}{n}$$
mannshah1211
30.01.2025 08:44
Been a while since I posted here...
For even $n$: Of course, for even $n$, we can put $(a, -a, \dots, a, -a)$ to get $0 \ge t_n$, and $t_n \ge 0$ as well, because $t_n = 0$ satisfies (as LHS is always positive). So, $t_n = 0$ in this case.
For odd $n$: I claim that $t_n = 2/n$.
Bound. Let the LHS be $M$, and the RHS be $x$. We can assume without loss of generality that $a_1 = x$. From the inequalities $-M \le a_i + a_{i + 1} \le M$ for $1 \le i \le n - 1$, we can inductively get bounds on $a_i$ depending on the parity of $i$. In particular, since $n$ is odd, we have $-(n - 1)M + x \le a_n \le (n - 1)M + x$. So, $a_n + a_1 = a_n + x \in [-(n - 1)M + 2x, (n - 1)M + 2x]$. But we also have $a_n + a_1 \in [-M, M]$. Thus, in order for us to have a valid solution for $a_i$, these two intervals must intersect. In particular, we have $-(n - 1)M + 2x \le M$, so $2x \le nM$, so $x \le nM/2$ and similarly $x \ge -nM/2$, which gives the bound.
Construction. It's easy to see that $(a, -3a, 5a, \dots, (-1)^{(n + 1)/2}na, \dots, 5a, -3a, a)$ for any $a$ works, as all adjacent sums have modulus $2a$, and the maximum absolute value is $na$, so $t_n = 2/n$ is also achievable.