## Romanian TST 2011 Problem 2

Denote .

Prove that:

a) For any positive integer there exists an arithmetic progression of length in .

b) Prove that does not contain a infinite length arithmetic progression.

**Proof: **a) Kronecker’s theorem states that is dense in , therefore, for there exists such that . For , we have , which means that , and we have found numbers in which form an arithmetic progression.

b) Suppose contains the infinite length progression . Therefore, we have . Therefore have the same integer part, which means that . This leads us to , an interval which contains at most one integer. This shows us that is an arithmetic progression, .

Rewriting the equalities above we get which shows us that . Divide by and let to get that is rational. Contradiction.

Obviously, instead of there could be any irrational number we want for part a). The well known van der Waerden theorem states that any partition of the positive integers into two or more parts has a part which contains arbitrarily long arithmetic progression. There is another well known problem, namely that if then form a partition of the positive integers. If neither nor contains any infinite arithmetic progression, by the arguments above. Therefore, the in the van der Waerden theorem we cannot state that there could be a set of the partition which contains an infinite arithmetic progression.

There are some flaws, in the proof and the final paragraph.

1. It should be , not ".

2. "Obviously, instead of there could be any irrational number we want." Surely, for point a), by the same Kronecker, or your Van der Waerden, argument; maybe (!?!) for point b), but not with the proof above, since we use the fact that between and there exists (at most) one integer. Change with an irrational , and this is no more true.

3. Thus your example using the Beatty sequence is flawed too, since for follows . However, it is elementary we can partition the positive integers into two classes , , so that if we index the elements of , respectively , in increasing order, the difference between consecutively indexed elements is not bounded, not for , nor for . But clearly then neither class can contain an infinite arithmetic progression.

I appreciate your comments and corrections. I was in a hurry when I posted the solution and therefore stated some facts without thinking very thoroughly how to prove them. I will correct the errors.

Thank you.

In fact, point b) is true for any irrational larger than 1, so the construct using Beatty’s theorem becomes valid.

(Question – what delimiters should be used to get latex-like formulae? using $ signs around does not seem to work).

To use the latex environment you put the delimiters

$latexin the beginning and$in the end.Can you give some ideas to why point b) is true for any irrational greater than ?

Thank you.

Let be irrational, and define . Assume there exists an infinite arithmetic progression (of positive integer ratio) . We may further assume that (or else we could pick , so that ). But the set is dense in , thus there exists such that

.

Denote .

That means . On one hand, it follows

$latex \displaystyle \lfloor n\lambda \rfloor a + Nr – \{\lambda\} + \lambda \geq a + Nr + 1$ (since ), thus

.

But then, the term cannot belong to , in contradiction with the assumption made, so does not contain an infinite arithmetic progression.

There are some bugs with wordpress latex. For example, when you type symbols < and > in some kind of code, the compiler thinks of them as html. I avoid using those. The second subtle bug is that when you type a latex formula, you are not allowed to have a double space, or else, the formula will not be displayed.

I have corrected some of your previous comment. Please see if it is ok.

Thank you.

Hi,

Just for interest do you have the other problems of the Romanian tst 2011? I saw 4 on here but surely there are more?

Thank you.

I have some more problems. I’ll try and post them soon.