https://artofproblemsolving.com/wiki/index.php?title=1991_IMO_Problems/Problem_6&feed=atom&action=history 1991 IMO Problems/Problem 6 - Revision history 2021-06-16T12:21:55Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=1991_IMO_Problems/Problem_6&diff=98827&oldid=prev Tchurch: created page; gave one argument and linked to second argument by Osmun Nal 2018-11-21T21:13:48Z <p>created page; gave one argument and linked to second argument by Osmun Nal</p> <p><b>New page</b></p><div>== Problem ==<br /> An infinite sequence &lt;math&gt;x_0, x_1, x_2,\ldots&lt;/math&gt; of real numbers is said to be ''bounded'' if there is a constant &lt;math&gt;C&lt;/math&gt; such that &lt;math&gt;|x_i| \leq C&lt;/math&gt; for every &lt;math&gt;i \geq 0&lt;/math&gt;.<br /> <br /> Given any real number &lt;math&gt;a &gt; 1&lt;/math&gt;, construct a bounded infinite sequence &lt;math&gt;x_0,x_1,x_2,\ldots&lt;/math&gt; such that &lt;math&gt;|x_i-x_j|\cdot |i-j|^a\geq 1&lt;/math&gt; for every pair of distinct nonnegative integers &lt;math&gt;i,j&lt;/math&gt;.<br /> <br /> == Solution 1 ==<br /> Since &lt;math&gt;a&gt;1&lt;/math&gt;, the series &lt;math&gt;\sum_{k=1}^\infty\frac{1}{k^a}&lt;/math&gt; is convergent; let &lt;math&gt;L&lt;/math&gt; be the sum of this convergent series. Let &lt;math&gt;I\subset \mathbb{R}&lt;/math&gt; be the interval &lt;math&gt;[-L,L]&lt;/math&gt; (or any bounded subset of measure &lt;math&gt;\geq 2L&lt;/math&gt;).<br /> <br /> <br /> Suppose that we have chosen points &lt;math&gt;x_0,x_1,\ldots,x_{m-1}&lt;/math&gt; satisfying <br /> <br /> &lt;math&gt;\qquad(\ast)\quad |x_i-x_j|\cdot |i-j|^a\geq 1&lt;/math&gt;<br /> <br /> for all distinct &lt;math&gt;i,j&lt;m&lt;/math&gt;. We show that we can choose &lt;math&gt;x_m\in I&lt;/math&gt; such that &lt;math&gt;(\ast)&lt;/math&gt; holds for all distinct &lt;math&gt;i,j\leq m&lt;/math&gt;. The only new cases are when one number (WLOG &lt;math&gt;i&lt;/math&gt;) is equal to &lt;math&gt;m&lt;/math&gt;, so we must guarantee that &lt;math&gt;|x_m-x_j|\cdot |m-j|^a\geq 1&lt;/math&gt; for all &lt;math&gt;0\leq j&lt;m&lt;/math&gt;.<br /> <br /> Let &lt;math&gt;U_j&lt;/math&gt; be the interval &lt;math&gt;(x_j-\frac{1}{|m-j|^a},x_j+\frac{1}{|m-j|^a})&lt;/math&gt;, of length &lt;math&gt;\frac{2}{|m-j|^a}&lt;/math&gt;. The points that are valid choices for &lt;math&gt;x_m&lt;/math&gt; are precisely the points of &lt;math&gt;I\setminus(U_0\cup \cdots \cup U_{m-1})&lt;/math&gt;, so we must show that this set is nonempty. The total length &lt;math&gt;\mu(U_0\cup \cdot\cup U_{m-1})&lt;/math&gt; is at most the sum of the lengths &lt;math&gt;\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}&lt;/math&gt;. This is &lt;math&gt;2\sum_{k=1}^m\frac{1}{k^a}&lt;2\sum_{k=1}^\infty \frac{1}{k^a}=2L&lt;/math&gt;.<br /> <br /> Therefore the total measure of &lt;math&gt;U_0\cup \cdots \cup U_{m-1}&lt;/math&gt; is &lt;math&gt;&lt;2L=\mu(I)&lt;/math&gt;, so &lt;math&gt;I\setminus(U_0\cup \cdots \cup U_{m-1})&lt;/math&gt; has positive measure and thus is nonempty. Choosing any &lt;math&gt;x_m\in I\setminus(U_0\cup \cdots \cup U_{m-1})&lt;/math&gt; and continuing by induction constructs the desired sequence.<br /> <br /> == Solution 2 ==<br /> The argument above would not work for &lt;math&gt;a=1&lt;/math&gt;, since &lt;math&gt;{\textstyle\sum \frac{1}{k^a}}&lt;/math&gt; only converges for &lt;math&gt;a&gt;1&lt;/math&gt;. But Osmun Nal argues [https://www.youtube.com/watch?v=3v3CMQS_5Cc in this video] that &lt;math&gt;x_k=k\sqrt{2}-\lfloor k\sqrt{2}\rfloor&lt;/math&gt; satisfies the stronger inequality &lt;math&gt;|x_i-x_j|\cdot |i-j|\geq 1&lt;/math&gt; for all distinct &lt;math&gt;i,j&lt;/math&gt;; in other words, this sequence simultaneously solves the problem for all &lt;math&gt;a\geq 1&lt;/math&gt; simultaneously.</div> Tchurch