2

For each real number $x$, let $[x]$ be the largest integer less than or equal to $x$. For example, $$[5] = 5$$

$$[7.9] = 7,$$ and $$[−2.4] = −3.$$

An arithmetic progression of length $k$ is a sequence $a_1, a_2, \dots, a_k$ with the property that there exists a real number $b$ such that $a_{i+1} − a_i = b$ for each $1 \leq i \leq k − 1.$

Let $\alpha > 2$ be a given irrational number. Let $S = \{[n · α] : n ∈ Z\}$, the set of all integers that are equal to $[n \alpha]$ for some integer $n$.

(a) Prove that for any integer $m \geq 3$, there exist m distinct numbers contained in $S$ which form an arithmetic progression of length $m$.

(b) Prove that there exist no infinite arithmetic progressions contained in $S$.

I'm thinking that for (a), some application pigeonhole principle can be considered... but otherwise, I don't really know how to prove this.

Some suggestions on a strategy would be awesome. Thanks.

vociferous_rutabaga
  • 4,591
user164403
  • 939
  • How familiar are you with the proof that the set of fractional parts ${{n\alpha}}_{n \in \mathbb N}$ is dense in the unit interval? – Erick Wong Aug 18 '14 at 03:15
  • Not very familiar at all... – user164403 Aug 18 '14 at 14:14
  • By the way, how does this relate to Number Theory? I know only very elementary Number Theory, so just wondering if there are some good books that cover these types of Number Theory questions. – user164403 Aug 18 '14 at 15:50

1 Answers1

3

Outline: We want to construct an arithmetic sequence of length $n$ that is a subsequence of the sequence $(\lfloor i\alpha\rfloor)$.

For $i=1,2,3, \dots, 10n+1$, let $b_i$ be the fractional part of $i\alpha$, that is, $i\alpha-\lfloor i\alpha\rfloor$. These fractional parts are all distinct, since $\alpha$ is irrational. By the Pigeonhole Principle, there exist $i$ and $j$ with $i\lt j$ such that $|b_j-b_i|\lt \frac{1}{10n}$. Let $k=j-i$. Then either (i) $b_k\gt 1-\frac{1}{10n}$ or (i) $b_k\lt \frac{1}{10n}$.

We look first at case (i). Consider the numbers $k\alpha$, $2k\alpha$, $3k\alpha$ and so on up to $nk\alpha$. The fractional parts of these are slowly decreasing. Thus the numbers $\lfloor k\alpha\rfloor$, $\lfloor 2k\alpha\rfloor$, $\lfloor 3k\alpha\rfloor$, and so on up to $\lfloor nk\alpha\rfloor$ form an arithmetic progression of length $n$. There is a lot of slack, we can continue well beyond $\lfloor nk\alpha\rfloor$.

Case (ii) is essentially the same, except that the fractional parts of the $ik\alpha$ slowly increase instead of decreasing.

The argument that our sequence has no infinite arithmetic progression uses similar ideas.

André Nicolas
  • 507,029
  • Would it be essential to apply the Pigeonhole Principle? I'm not used to using it, so I'm just wondering if there are other ways. Also, when do you know that a problem uses the Pigeonhole Principle? Is there anything that 'ticks', and you know that you have to use the Pigeonhole Principle? Are there any clues that show this in the question when not explicitly stated? – user164403 Sep 06 '14 at 04:19
  • Well, I guess we do not have to mention the Pigeonhole Principle explicitly. But we will have to use it implicitly, since the $\alpha$ is general. It comes up whenever we are interested in the distribution of fractional parts. Here it was integer parts, but the technique was worth trying, and works. An indication that Pigeonhole might be useful is if the problem says that a set has more than $k$ elements, then a certain nice thing happens. The problem above, however, does not really have that shape. – André Nicolas Sep 06 '14 at 05:20
  • What type of math is this? I'm very interested in it and would like to learn more by checking out resources pertaining to that aspect of math. – user164403 Sep 30 '14 at 03:42
  • It belongs, more or less, to Diophantine Approximation. – André Nicolas Sep 30 '14 at 03:45
  • Are there any good books on those kinds of questions? This question was from a Math Challenge, and this challenge stated that to prepare, one should go over such topics as sequences and series, which I thought was to be in real analysis. – user164403 Sep 30 '14 at 16:40
  • Some books meant to be used in Olympiad preparation may be useful. I kind of like Engel, Problem Solving Strategies, but there are others. You may want to look at Ivan Niven's short books on Rational and Irrational Numbers, also on Diophantine Approximation. But the latter two are not "problem-solving" oriented. – André Nicolas Sep 30 '14 at 16:52
  • What about these two books: Counterexamples in Analysis, and Paul Zeitz's Problem Solving book? – user164403 Oct 01 '14 at 20:52
  • Both nice books. I like Engel better than Zeitz. Counterexamples in Analysis is a great resource, though not so much for problem-solving. While we are talking of books, I recommend you look at Michael Steele's book on the Cauchy-Schwarz Inequality. – André Nicolas Oct 01 '14 at 20:57
  • That book is about inequalities though isn't it? Or can it be applied to questions such as these? i have not read it yet but i am interested. – user164403 Oct 02 '14 at 00:42
  • It is about inequalities, yes. But it has "problem-solving" features, that happen to link together into a systematic view of something important. One weakness of pure Olympiad-oriented problem solving is that Olympiad problems fall in a very narrow range, some of which, including most of the geometry problems, represents moribund mathematics. – André Nicolas Oct 02 '14 at 00:49