Maths Olympiad Prep

Library / /1 of 70

Algebra Difficulty 7.2 National Olympiad, round 2 Prove it Romania

Prove that the set S={nπ:n=0,1,2,3,}S = \{\lfloor n\pi \rfloor : n = 0, 1, 2, 3, \dots \} contains arithmetic progressions of any finite length, but no infinite arithmetic progressions.

Solution

If xx is a real number, let {x}=xx\{x\} = x - \lfloor x \rfloor denote the fractional part of xx. Given an integer number m3m \ge 3, there exists a positive integer number nn such that {nπ}<1/m\{n\pi\} < 1/m, for the set {kπ:k=0,1,2,3,}\{k\pi : k = 0, 1, 2, 3, \dots\} is dense in the closed unit interval [0,1][0, 1]. Consequently,
knπ=knπ+k{nπ}=knπ+k{nπ}=knπ,k=1,2,,m, \lfloor kn\pi \rfloor = \lfloor k \lfloor n\pi \rfloor \rfloor + \lfloor k\{n\pi\} \rfloor = k \lfloor n\pi \rfloor + \lfloor k\{n\pi\} \rfloor = k \lfloor n\pi \rfloor, \quad k = 1, 2, \dots, m,
so nπ,2nπ,,mnπ\lfloor n\pi \rfloor, \lfloor 2n\pi \rfloor, \dots, \lfloor mn\pi \rfloor are mm numbers in SS in arithmetic progression with ratio nπ\lfloor n\pi \rfloor.

Suppose, if possible, that SS contains an infinite arithmetic progression nkπ\lfloor n_k \pi \rfloor, k=0,1,2,3,k = 0, 1, 2, 3, \dots, with (integral) ratio rr, where the nkn_k form a strictly increasing sequence of positive integer numbers. Write nkπ=n0π+kr+{nkπ}n_k \pi = \lfloor n_0 \pi \rfloor + kr + \{n_k \pi\} to deduce that rr is positive and
nk+1nk=r+{nk+1π}{nkπ}π(r1π,r+1π). n_{k+1} - n_k = \frac{r + \{n_{k+1}\pi\} - \{n_k\pi\}}{\pi} \in \left( \frac{r-1}{\pi}, \frac{r+1}{\pi} \right).
The length of this interval is less than 11, so nk+1nk=nn_{k+1} - n_k = n for some positive integer nn and all indices kk. Hence, nk=n0+knn_k = n_0 + kn, so nk/kknn_k/k \xrightarrow{k \to \infty} n. On the other hand, nk/kkr/πn_k/k \xrightarrow{k \to \infty} r/\pi, so π=r/n\pi = r/n which contradicts irrationality of π\pi.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.