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"

(Created page with "Find the largest real number <math>C</math> such that for any positive integer <math>n</math> and any real numbers <math>x_1, x_2, \ldots, x_n</math>, the following inequality...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
 +
== Problem ==
 
Find the largest real number <math>C</math> such that for any positive integer <math>n</math> and any real numbers <math>x_1, x_2, \ldots, x_n</math>, the following inequality holds:
 
Find the largest real number <math>C</math> such that for any positive integer <math>n</math> and any real numbers <math>x_1, x_2, \ldots, x_n</math>, the following inequality holds:
 
<cmath>
 
<cmath>
Line 4: Line 5:
 
</cmath>
 
</cmath>
 
== Solution 1 ==  
 
== Solution 1 ==  
 +
Define the <math>n \times n</math> matrix <math>A_n</math> as follows:
 +
<cmath>
 +
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)
 +
</cmath>
 +
 +
The problem simplifies to finding the smallest real number <math>C</math> such that for all <math>n \in \mathbb{N}^*</math> and any vector <math>x \in \mathbb{R}^n</math>, the following inequality holds:
 +
<cmath>
 +
x^T A_n x \geq C x^T x
 +
</cmath>
 +
 +
In other words, find the real number <math>C</math> such that:
 +
<cmath>
 +
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}
 +
</cmath>
 +
Given that <math>A_n</math> is not easily invertible directly, but is invertible (as it is a sparse matrix):
 +
<cmath>
 +
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)
 +
</cmath>
 +
 +
Since the inverse has non-zero entries:
 +
<cmath>
 +
\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}
 +
</cmath>
 +
 +
For the eigenvalues <math>\mu</math> of <math>A_n</math> :
 +
<cmath>
 +
\frac{1}{2}+\frac{1}{2 n+2} \leq \mu-1 \leq \frac{1}{2}+\frac{1}{2 n+2}
 +
</cmath>
  
 +
Thus:
 +
<cmath>
 +
0 \leq \mu \leq 2
 +
</cmath>
 +
Given that <math>A_n^{-1}</math> is invertible, <math>\mu \neq 0</math>, therefore:
 +
<cmath>
 +
\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}
 +
</cmath>
 +
 +
For a specific <math>y \in \mathbb{R}^n, y=[1,-1,1,-1, \ldots]^T \in \mathbb{R}^n</math>, we have:
 +
<cmath>
 +
\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}
 +
</cmath>
 +
 +
In conclusion:
 +
<cmath>
 +
\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}
 +
</cmath>
  
 +
Therefore, the maximum value of the real number <math>C</math> is <math>\frac{1}{2}</math>.
  
 +
~dalian xes|szm
 
==See also==
 
==See also==
−
{{CMO box|year=2023|before=First Problem|num-a=2|n=I}}
+
{{CMO box|year=2023|num-b=1|num-a=3}}

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"