Problem A. 628. (November 2014)
A. 628. Is it true that for every infinite sequence \(\displaystyle x_1,x_2,\ldots\) of integers satisfying \(\displaystyle |x_{k+1}-x_k|=1\) for every positive integer \(\displaystyle k\), there exists a sequence \(\displaystyle k_1<k_2<\ldots<k_{2014}\) of positive integers such that as well the indices \(\displaystyle k_1,k_2,\ldots,k_{2014}\) as the numbers \(\displaystyle x_{k_1},x_{k_2},\ldots,x_{k_{2014}}\) (in this order) form arithmethic progressions?
Proposed by: E. Csóka, Warwick and Ben Green, Oxford
(5 pont)
Deadline expired on December 10, 2014.
Solution. The answer is NO. We provide a sequence whose neighboring terms have difference \(\displaystyle \pm 1\), but for which there do not exist appropriate indices \(\displaystyle k_1<\ldots<k_{2014}\).
Define
\(\displaystyle f(t) = \sum_{n=1}^\infty 50^n \sin\frac{t}{100^n} \)
(this series converges for all real \(\displaystyle t\), because \(\displaystyle \left|50^n \sin\frac{t}{100^n}\right|<\frac{|t|}{2^n}\)), and for each positive integer \(\displaystyle k\), let \(\displaystyle x_k\) be an integer with the same parity as \(\displaystyle k\) and \(\displaystyle \big|x_k-f(k)\big|\le1\). We claim that this sequence works.
First, we verify that \(\displaystyle |x_{k+1}-x_k|=1\). It is well-known that for any distinct reals \(\displaystyle u,v\), \(\displaystyle \big|\sin u-\sin v\big|<|u-v|\), hence
\(\displaystyle \big|f(u)-f(v)\big| = \left| \sum_{n=1}^\infty 50^n \bigg(\sin\frac{u}{100^n}-\sin\frac{u}{100^n}\bigg)\right| \le \sum_{n=1}^\infty 50^n \left| \sin\frac{u}{100^n}-\sin\frac{u}{100^n}\right| < \)
\(\displaystyle < \sum_{n=1}^\infty 50^n \frac{|u-v|}{100^n} = |u-v| \sum_{n=1}^\infty \left(\frac12\right)^n = |u-v|. \)
Applying this in the case \(\displaystyle (u,v)=(k,k+1)\), we find
\(\displaystyle |x_k-x_{k+1}| \le \big|x_k-f(k)\big| + \big|f(k)-f(k+1)\big| + \big|f(k+1)-x_{k+1}\big| < 1+1+1 = 3. \)
But since \(\displaystyle x_k-x_{k+1}\) is odd, we must have \(\displaystyle |x_k-x_{k+1}|=1\).
Now consider an arithmetic progression \(\displaystyle k_1<\ldots<k_{2014}\) with difference \(\displaystyle d\). Note that \(\displaystyle d\) lies between two neighboring powers of \(\displaystyle 100\), so \(\displaystyle 100^{m-1}\le d \le 100^m\) for some positive integer \(\displaystyle m\). Define \(\displaystyle h\) to be the largest positive integer with \(\displaystyle hd\le 100^m\); then we have \(\displaystyle h\le 100\), but
\(\displaystyle \frac{100^m}2 < hd \le 100^m. \)
Note that \(\displaystyle \frac{k_{101}}{100^m}, \frac{k_{102}}{100^m}, \ldots, \frac{k_{800}}{100^m}\) form an arithmetic progression of difference at most \(\displaystyle 1\) (and also that the first and last term have difference \(\displaystyle >2\pi\)), hence for some index \(\displaystyle 101\le i\le 800\), the remainder of \(\displaystyle \frac{k_i}{100^m}\) mod \(\displaystyle 2\pi\) lies in the range \(\displaystyle \left(\frac{\pi}{3};\frac{2\pi}{3}\right)\); for this index, \(\displaystyle \sin\frac{k_i}{100^m}>\sin\frac\pi3\). Fix such an index \(\displaystyle i\), and consider the quantity
\(\displaystyle \Delta = (x_{k_i+hd} - x_{k_i}) - (x_{k_i} - x_{k_i-hd}) = x_{k_i+hd} - 2x_{k_i} + x_{k_i-hd}. \)
If \(\displaystyle x_{k_i-hd}, x_{k_i}, x_{k_i+hd}\) form an arithmetic progression, then \(\displaystyle \Delta=0\). We will now proceed to show that \(\displaystyle \Delta\neq 0\), obtaining a contradiction. For the sake of simplicity, use the notation \(\displaystyle K=k_i\) and \(\displaystyle D=hd\). Then \(\displaystyle \frac12<\frac{D}{100^m}\le1\), \(\displaystyle 1\le K-D < K < K+D \le 900\), and
\(\displaystyle \Delta = x_{K+D} - 2x_K + x_{X-D}. \)
Let's substitute in the definition of the sequence, write down \(\displaystyle \Delta\) in terms of \(\displaystyle f\), and bound from below using the \(\displaystyle m\)-th term:
\(\displaystyle |\Delta| \ge \big| f(K+D) - 2f(K) + f(K-D) \big| - 4 = \left| \sum_{n=1}^\infty 50^n\bigg(\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg)\right| -4 \ge \)
\(\displaystyle \ge 50^m\bigg|\sin\frac{K+D}{100^m}-2\sin\frac{K}{100^m}+\sin\frac{K-D}{100^m}\bigg| - \)
\(\displaystyle -\sum_{n=1}^{m-1} 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| -\sum_{n=m+1}^\infty 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| -4. \) | \(\displaystyle (1) \) |
Applying the identity
\(\displaystyle \sin(a+b)-2\sin a +\sin(a-b) = \big(\sin(a+b)-\sin a\big)-\big(\sin a-\sin(a-b)\big) = \)
\(\displaystyle = 2\sin\frac{b}2\bigg(\cos\frac{2a+b}2-\cos\frac{2a-b}2\bigg) = - 4 \sin^2\frac{b}2 \sin a \) | \(\displaystyle (2) \) |
provides the following lower estimate of the \(\displaystyle m\)-th term:
\(\displaystyle 50^m\bigg|\sin\frac{K+D}{100^m}-2\sin\frac{K}{100^m}+\sin\frac{K-D}{100^m}\bigg| = 50^m \cdot 4\sin^2\frac{D}{2\cdot 100^m}\sin\frac{K}{100^m} > \)
\(\displaystyle > 50^m \cdot 4\sin^2\frac14\cdot\sin\frac\pi3 > \frac{50^m}5. \) | \(\displaystyle (3) \) |
Moreover, using \(\displaystyle (2)\) again, we have
\(\displaystyle \sum_{n=m+1}^\infty 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| = \sum_{n=m+1}^\infty 50^n \cdot 4\sin^2\frac{D}{2\cdot 100^n}\left|\sin\frac{K}{100^n}\right| < \)
\(\displaystyle < \sum_{n=m+1}^\infty 50^n \cdot 4\left(\frac{D}{2\cdot 100^n}\right)^2\cdot 1 < \sum_{n=m+1}^\infty 50^n \cdot 4\left(\frac{100^m}{2\cdot 100^n}\right)^2 = 50^m \sum_{\ell=1}^\infty \left(\frac1{200}\right)^\ell = \frac{50^m}{199} < \frac{50^m}{100}. \) | \(\displaystyle (4) \) |
Estimating the value of all the sines by \(\displaystyle 1\) for small indices (i.e. when \(\displaystyle n<m\)), we find
\(\displaystyle \sum_{n=1}^{m-1} 50^n\bigg|\sin\frac{K+D}{100^n}-2\sin\frac{K}{100^n}+\sin\frac{K-D}{100^n}\bigg| \le \sum_{n=1}^{m-1} 50^n \cdot 4 = \)
\(\displaystyle = 50^m\cdot 4\sum_{\ell=1}^m \left(\frac1{50}\right)^\ell < 50^m\cdot 4\sum_{\ell=1}^\infty \left(\frac1{50}\right)^\ell = 50^m\cdot \frac4{49} < \frac{50^m}{10}. \) | \(\displaystyle (5) \) |
Finally, putting estimates \(\displaystyle (3-5)\) into \(\displaystyle (1)\), we obtain the contradiction
\(\displaystyle |\Delta| > \frac{50^m}{5} - \frac{50^m}{100} - \frac{50^m}{10} - 4 = 50^m\cdot\frac{9}{100} - 4 > 0. \)
Therefore, \(\displaystyle x_{k_1},\ldots,x_{k_{2014}}\) can never form an arithmetic progression.
Statistics:
2 students sent a solution. 0 point: 2 students.
Problems in Mathematics of KöMaL, November 2014