Maths Olympiad Prep

Library / Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads /2 of 80

Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

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}=x−⌊x⌋\{x\} = x - \lfloor x \rfloor denote the fractional part of xx. Given an integer number m≥3m \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π⌋=⌊k⌊nπ⌋⌋+⌊k{nπ}⌋=k⌊nπ⌋+⌊k{nπ}⌋=k⌊nπ⌋,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+1−nk=r+{nk+1π}−{nkπ}π∈(r−1π,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+1−nk=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/k→k→∞nn_k/k \xrightarrow{k \to \infty} n. On the other hand, nk/k→k→∞r/π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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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