Art of Problem Solving
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

1991 IMO Problems/Problem 6: Difference between revisions

Newer edit →
created page; gave one argument and linked to second argument by Osmun Nal
 
Tomasdiaz (talk | contribs)
editor
1,840 edits
Line 20: Line 20:
== Solution 2 ==
== Solution 2 ==
The argument above would not work for <math>a=1</math>, since <math>{\textstyle\sum \frac{1}{k^a}}</math> only converges for <math>a>1</math>. But Osmun Nal argues [https://www.youtube.com/watch?v=3v3CMQS_5Cc in this video] that <math>x_k=k\sqrt{2}-\lfloor k\sqrt{2}\rfloor</math> satisfies the stronger inequality <math>|x_i-x_j|\cdot |i-j|\geq 1</math> for all distinct <math>i,j</math>; in other words, this sequence simultaneously solves the problem for all <math>a\geq 1</math> simultaneously.
The argument above would not work for <math>a=1</math>, since <math>{\textstyle\sum \frac{1}{k^a}}</math> only converges for <math>a>1</math>. But Osmun Nal argues [https://www.youtube.com/watch?v=3v3CMQS_5Cc in this video] that <math>x_k=k\sqrt{2}-\lfloor k\sqrt{2}\rfloor</math> satisfies the stronger inequality <math>|x_i-x_j|\cdot |i-j|\geq 1</math> for all distinct <math>i,j</math>; in other words, this sequence simultaneously solves the problem for all <math>a\geq 1</math> simultaneously.
==See Also==
{{IMO box|year=1991|num-b=5|after=Last Question}}
[[Category:Olympiad Geometry Problems]]
[[Category:3D Geometry Problems]]

Revision as of 23:38, 16 November 2023

Problem

An infinite sequence $x_0, x_1, x_2,\ldots$ of real numbers is said to be bounded if there is a constant $C$ such that $|x_i| \leq C$ for every $i \geq 0$.

Given any real number $a > 1$, construct a bounded infinite sequence $x_0,x_1,x_2,\ldots$ such that $|x_i-x_j|\cdot |i-j|^a\geq 1$ for every pair of distinct nonnegative integers $i,j$.

Solution 1

Since $a>1$, the series $\sum_{k=1}^\infty\frac{1}{k^a}$ is convergent; let $L$ be the sum of this convergent series. Let $I\subset \mathbb{R}$ be the interval $[-L,L]$ (or any bounded subset of measure $\geq 2L$).


Suppose that we have chosen points $x_0,x_1,\ldots,x_{m-1}$ satisfying

$\qquad(\ast)\quad |x_i-x_j|\cdot |i-j|^a\geq 1$

for all distinct $i,j<m$. We show that we can choose $x_m\in I$ such that $(\ast)$ holds for all distinct $i,j\leq m$. The only new cases are when one number (WLOG $i$) is equal to $m$, so we must guarantee that $|x_m-x_j|\cdot |m-j|^a\geq 1$ for all $0\leq j<m$.

Let $U_j$ be the interval $(x_j-\frac{1}{|m-j|^a},x_j+\frac{1}{|m-j|^a})$, of length $\frac{2}{|m-j|^a}$. The points that are valid choices for $x_m$ are precisely the points of $I\setminus(U_0\cup \cdots \cup U_{m-1})$, so we must show that this set is nonempty. The total length $\mu(U_0\cup \cdot\cup U_{m-1})$ is at most the sum of the lengths $\mu(U_0)+\cdots+\mu(U_{m-1})=\frac{2}{m^a}+\frac{2}{(m-1)^a}+\cdots+\frac{2}{2^a}+\frac{2}{1^a}$. This is $2\sum_{k=1}^m\frac{1}{k^a}<2\sum_{k=1}^\infty \frac{1}{k^a}=2L$.

Therefore the total measure of $U_0\cup \cdots \cup U_{m-1}$ is $<2L=\mu(I)$, so $I\setminus(U_0\cup \cdots \cup U_{m-1})$ has positive measure and thus is nonempty. Choosing any $x_m\in I\setminus(U_0\cup \cdots \cup U_{m-1})$ and continuing by induction constructs the desired sequence.

Solution 2

The argument above would not work for $a=1$, since ${\textstyle\sum \frac{1}{k^a}}$ only converges for $a>1$. But Osmun Nal argues in this video that $x_k=k\sqrt{2}-\lfloor k\sqrt{2}\rfloor$ satisfies the stronger inequality $|x_i-x_j|\cdot |i-j|\geq 1$ for all distinct $i,j$; in other words, this sequence simultaneously solves the problem for all $a\geq 1$ simultaneously.

See Also

1991 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=1991_IMO_Problems/Problem_6&oldid=204226"