Home > Algebra, IMO, Problem Solving > Romanian TST 2011 Problem 2

Romanian TST 2011 Problem 2

Denote S=\{\lfloor n \pi \rfloor : n \in \Bbb{N} \}.

Prove that:

a) For any positive integer m \geq 3 there exists an arithmetic progression of length m in S.

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

Proof: a) Kronecker’s theorem states that \{ n \pi \} is dense in [0,1], therefore, for q \in \Bbb{N},\ q \geq 3 there exists k such that p < k \pi < p+\frac{1}{q}. For s=1,2,...,q, we have ps < ks \pi < ps+\frac{s}{q}\leq ps+1, which means that \lfloor ks \pi \rfloor =ps,\ s=1,2,...,q, and we have found q numbers in S which form an arithmetic progression.

b) Suppose S contains the infinite length progression \lfloor n_k \pi \rfloor=a+kb,\ a,b \in \Bbb{N}, k \geq 1. Therefore, we have a+kb < n_k \pi <a+kb+1,\ \forall k \geq 1. Therefore n_k \pi+b, n_{k+1}\pi have the same integer part, which means that -1<\pi(n_{k+1}-n_k)-b<1,\ \forall k \geq 1. This leads us to (b-1)/\pi < n_{k+1}-n_k < (b+1)/\pi, an interval which contains at most one integer. This shows us that (n_k)_k is an arithmetic progression, n_k=c+dk,\ c,d \in \Bbb{N}.

Rewriting the equalities above we get a+kb< (c+dk)\pi <a+bk+1 which shows us that a-c\pi <k(d\pi-b)<a-c\pi+1,\ \forall k \geq 1. Divide by k and let k \to \infty to get that \pi is rational. Contradiction.

Obviously, instead of \pi 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 \frac{1}{a}+\frac{1}{b}=1 then A= \{ \lfloor na\rfloor\}, B=\{ \lfloor nb \rfloor\} form a partition of the positive integers. If a=\pi neither A nor B 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.

  1. Dan Schwarz
    April 22, 2011 at 1:31 am

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

    1. It should be -1 < \pi(n_{k+1} - n_k) - b < 1, not "0 < \pi(n_{k+1} - n_k) - b <1.

    2. "Obviously, instead of \pi 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 (b-1)/\pi and (b+1)/\pi there exists (at most) one integer. Change \pi with an irrational 0 < \lambda < 2, and this is no more true.

    3. Thus your example using the Beatty sequence is flawed too, since for a=\pi follows b = \pi/(\pi - 1) < 2. However, it is elementary we can partition the positive integers into two classes A, B, so that if we index the elements of A, respectively B, in increasing order, the difference between consecutively indexed elements is not bounded, not for A, nor for B. But clearly then neither class can contain an infinite arithmetic progression.

    • April 22, 2011 at 11:20 am

      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.

  2. Dan Schwarz
    May 2, 2011 at 6:12 pm

    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).

    • May 3, 2011 at 7:44 am

      To use the latex environment you put the delimiters $latex in the beginning and $ in the end.

    • May 3, 2011 at 6:42 pm

      Can you give some ideas to why point b) is true for any irrational greater than 1?
      Thank you.

  3. Dan Schwarz
    May 7, 2011 at 1:38 pm

    Let \lambda > 1 be irrational, and define S = \{ \lfloor n\lambda \rfloor \ ; \ n \in \mathbb{N}\}. Assume there exists an infinite arithmetic progression (of positive integer ratio) A = \{a + nr \ ; \ n \in \mathbb{N}\} \subseteq S. We may further assume that 1\leq a<r (or else we could pick 1 \leq a^\prime  < r^\prime , so that A' = \{a' + nr' \ ; \ n \in \mathbb{N}\} \subseteq A). But the set \displaystyle \left \{ \left \{n\dfrac{\lambda} {r} \right \} \ ; \ n\in \mathbb{N}\right \} is dense in [0,1], thus there exists n such that
    \displaystyle 0 < \dfrac {a} {r} - \dfrac {\{\lambda\}} {r} < n\dfrac {\lambda} {r} - \left \lfloor n\dfrac {\lambda} {r} \right \rfloor < \dfrac {a} {r} < 1.
    Denote N = \left \lfloor n\dfrac {\lambda} {r} \right \rfloor.
    That means a + Nr - \{\lambda\} < n\lambda < a + Nr. On one hand, it follows
    $latex \displaystyle \lfloor n\lambda \rfloor a + Nr – \{\lambda\} + \lambda \geq a + Nr + 1$ (since \lambda - \{\lambda\} \geq 1), thus
    \displaystyle \lfloor (n+1)\lambda \rfloor \geq a + Nr + 1 > a + Nr.
    But then, the term a + Nr \in A cannot belong to S, in contradiction with the assumption made, so S does not contain an infinite arithmetic progression.

  4. May 7, 2011 at 5:12 pm

    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.

  5. abconjecture
    May 31, 2011 at 8:21 am

    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.

    • May 31, 2011 at 10:48 am

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

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: