Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 CMO Problems/Problem 2"
 
(No difference)

Latest revision as of 05:37, 25 May 2024

Problem

Find the largest real number $C$ such that for any positive integer $n$ and any real numbers $x_1, x_2, \ldots, x_n$, the following inequality holds: \[\sum_{i=1}^n \sum_{j=1}^n(n-|j-i|) x_i x_j \geq C \sum_{i=1}^n x_i^2\]

Solution 1

Define the $n \times n$ matrix $A_n$ as follows: \[A_n=\left(\begin{array}{cccccc} n & n-1 & n-2 & \cdots & 2 & 1 \\ 1 & n & n-1 & \cdots & 3 & 2 \\ 2 & 1 & n & \cdots & 4 & 3 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ n-2 & n-3 & n-4 & \cdots & n & n-1 \\ n-1 & n-2 & n-3 & \cdots & 1 & n \end{array}\right)\]

The problem simplifies to finding the smallest real number $C$ such that for all $n \in \mathbb{N}^*$ and any vector $x \in \mathbb{R}^n$, the following inequality holds: \[x^T A_n x \geq C x^T x\]

In other words, find the real number $C$ such that: \[C \leq \inf _{n \in \mathbb{N}^*} \inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}\] Given that $A_n$ is not easily invertible directly, but is invertible (as it is a sparse matrix): \[A_n^{-1}=\left(\begin{array}{cccccc} \frac{n+2}{2 n+2} & \frac{1}{2} & 0 & \cdots & 0 & \frac{1}{2 n+2} \\ -\frac{1}{2} & 1 & \frac{1}{2} & \cdots & 0 & 0 \\ 0 & -\frac{1}{2} & 1 & \frac{1}{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & -\frac{1}{2} & 1 & \frac{1}{2} \\ \frac{1}{2 n+2} & 0 & \cdots & 0 & -\frac{1}{2} & \frac{n+2}{2 n+2} \end{array}\right)\]

Since the inverse has non-zero entries: \[\inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}=\left(\sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}\]

For the eigenvalues $\mu$ of $A_n$ : \[\frac{1}{2}+\frac{1}{2 n+2} \leq \mu-1 \leq \frac{1}{2}+\frac{1}{2 n+2}\]

Thus: \[0 \leq \mu \leq 2\] Given that $A_n^{-1}$ is invertible, $\mu \neq 0$, therefore: \[\begin{gathered} 0<\mu \leq 2 \\ \sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x} \leq 2 \end{gathered}\]

For a specific $y \in \mathbb{R}^n, y=[1,-1,1,-1, \ldots]^T \in \mathbb{R}^n$, we have: \[\begin{gathered} y^T y=n \\ y^T A_n^{-1} y= \begin{cases}2(n-2)+\frac{2(n+2)}{n+1} & \text { if } n \text { is even } \\ 2(n-1) & \text { if } n \text { is odd }\end{cases} \\ \sup _n \sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x} \geq \sup _n \frac{y^T A_n y}{y^T y} \geq 2 \end{gathered}\]

In conclusion: \[\inf _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n x}{x^T x}=\inf _n\left(\sup _{\substack{x \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}=\left(\sup _{\substack{n \\ n \in \mathbb{R}^n \\ x \neq 0}} \frac{x^T A_n^{-1} x}{x^T x}\right)^{-1}=\frac{1}{2}\]

Therefore, the maximum value of the real number $C$ is $\frac{1}{2}$.

~dalian xes|szm

See also

2023 CMO(CHINA) (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All CMO(CHINA) Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_CMO_Problems/Problem_2&oldid=219687"