Maths Olympiad Prep

Library / /499 of 520

Number theory Difficulty 6.4 National olympiad Prove it

C4 For each real number xx, let [x][x] be the largest integer less than or equal to xx. For example, [5]=5,[7.9]=7[5]=5,[7.9]=7 and [2.4]=3[-2.4]=-3. An arithmetic progression of length kk is a sequence a1,a2,,aka_{1}, a_{2}, \ldots, a_{k} with the property that there exists a real number bb such that ai+1ai=ba_{i+1}-a_{i}=b for each 1ik11 \leq i \leq k-1.
Let α>2\alpha>2 be a given irrational number. Then S={[nα]:nZ}S=\{[n \cdot \alpha]: n \in \mathbb{Z}\}, is the set of all integers that are equal to [nα][n \cdot \alpha] for some integer nn.
(a) Prove that for any integer m3m \geq 3, there exist mm distinct numbers contained in SS which form an arithmetic progression of length mm.
(b) Prove that there exist no infinite arithmetic progressions contained in SS.

Solution

Solution
(a) We first prove the following statement: For each positive integer mm there exist positive integers nmn \leq m and xmx_{m} such that nαxm2\left|n \alpha-x_{m}\right|2 while n2>n1n_{2}>n_{1} we conclude that xm=[n2α][n1α][α]2x_{m}=\left[n_{2} \alpha\right]-\left[n_{1} \alpha\right] \geq[\alpha] \geq 2 is also a positive integer.
As proved above, for each integer m3m \geq 3, there exist positive integers nmn \leq m and xmx_{m} such that nαxm2\left|n \alpha-x_{m}\right|2 we conclude that for each iNi \in \mathbb{N} we have ni+22ni+1+ni=0n_{i+2}-2 n_{i+1}+n_{i}=0. So, n1α,n2α,,niα,n_{1} \alpha, n_{2} \alpha, \cdots, n_{i} \alpha, \cdots is itself an arithmetic progression. Therefore, the difference of the two arithmetic progressions is another infinite arithmetic progression: {n1α},{n2α},,{niα},\left\{n_{1} \alpha\right\},\left\{n_{2} \alpha\right\}, \cdots,\left\{n_{i} \alpha\right\}, \cdots.

However, the arithmetic progressions cannot be bounded, unless their ratio is 0 . Hence {n2α}={n1α}\left\{n_{2} \alpha\right\}=\left\{n_{1} \alpha\right\}, which yields that n2αn1α=[n2α][n1α]Zn_{2} \alpha-n_{1} \alpha=\left[n_{2} \alpha\right]-\left[n_{1} \alpha\right] \in \mathbb{Z} and therefore αQ\alpha \in \mathbb{Q}, which is a contradiction with our assumption (also note that n2n1n_{2} \neq n_{1} since they belong to an infinite arithmetic progression).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.