Prove that the set $S=\{\lfloor n\pi\rfloor \mid n=0,1,2,3,\ldots\}$ contains arithmetic progressions of any finite length, but no infinite arithmetic progressions. Vasile Pop
Problem
Source: 2011 Romania TST Problem 2
Tags: floor function, pigeonhole principle, arithmetic sequence, Ramsey Theory, number theory proposed, number theory
05.02.2012 01:18
van der Waerden's Theorem gives us the result of any finite length, so it suffices to show their exist no infinite sequences. Suppose $a, a+d, a + 2d,... \in S$ for some $a,d$ so in other words $a + nd \in S$ for all $n \in \mathbb{N}$. Let $[m]$ for a natural number $m$ denote $m$ modulo $\pi$, that is $[m] = m - \lfloor m/\pi \rfloor \pi$. Clearly $[d] > 0$ because that $\pi$ is irrational. Observe that $m \in S$ requires $[m] > \pi - 1$. Now again as $\pi$ is irrational, we have the sequence given by $\{[a + nd]\}_{n \ge 0}$ is dense in the set $(0, \pi)$ because it is an arithmetic progression of infinite length and it's difference is irrational with respect to the modulus ($\pi$). It immediately follows not every element of the sequence can be in $S$ and we are done.
05.03.2012 13:22
I think there is no need of such a powerful gun to attack the first part! Indeed, for a given positive integer $m$, by an easy use of pigeonhole principle one can show that there exists a $n\in \mathbb N$ such that $\{n\pi\}\le \frac{1}{m}$. (Here $\{x\}$ means the fractional part of $x$). now $\lfloor n\pi \rfloor, \lfloor 2n\pi \rfloor,...., \lfloor mn\pi \rfloor$ form an arithmetic progression of length $m$.
05.03.2012 17:55
Indeed the first part is an easy pigeonhole, but it's always nice to cite a big theorem to instantly kill an olympiad problem
05.03.2012 18:20
dinoboy wrote: Indeed the first part is an easy pigeonhole, but it's always nice to cite a big theorem to instantly kill an olympiad problem you're right, and I love to do this , but it's very disappointing if someone loses points in exams for doing this
10.04.2012 15:59
dinoboy wrote: van der Waerden's Theorem gives us the result of any finite length, so it suffices to show their exist no infinite sequences. So how does van der Waerden's Theorem apply here? vdW yields the existence of arithmetic progressions of any finite length in the set $S$ or in the complement of $S$. How do you then exclude that the progressions in the complement of $S$?
10.04.2012 17:47
Sorry actually I didn't mean van der Waerdan's Theorem. I meant Szemeredi's theorem.
02.05.2018 14:14
I have a hilarious question:What if $\pi <2$? If it is,is this problem still right???
10.05.2018 21:20
For all integers $n_1,n_2,n_3\in Z_+$ $2\lfloor n_2\pi\rfloor=\lfloor n_1\pi\rfloor+\lfloor n_3\pi\rfloor\iff 2n_2=n_1+n_3$
10.05.2018 21:26
CeuAzul wrote: I have a hilarious question:What if $\pi <2$? If it is,is this problem still right??? In proof of above post you only need fact $\pi >2$ and of course floor function features. So I think for all $\pi>2$ the theorem works.