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| - \)

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) = \)

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} > \)

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| < \)

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 = \)

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