Tuesday, January 30, 2007

Even, Odd, Even, Odd... Topic: Algebra/S&S. Level: AMC/AIME.

Problem: Show that the sequence $ \lfloor \sqrt{2} \rfloor, \lfloor 2\sqrt{2} \rfloor, \lfloor 3\sqrt{2} \rfloor, \ldots $ contains an infinte number of both even and odd integers. Furthermore, show that there can be at most two consecutive integers of the same parity.

Solution: Suppose their exists a finite number of either even or odd integers. Then we definitely have three integers of the same parity in a row. But since $ 1 < \sqrt{2} < 2 $, they must each differ by $ 2 $. Hence

$ \lfloor k\sqrt{2}\rfloor+2 = \lfloor (k+1)\sqrt{2} \rfloor $

$ \lfloor (k+1)\sqrt{2}\rfloor+2 = \lfloor (k+2)\sqrt{2} \rfloor $.

Adding the equalities together, we get

$ \lfloor k\sqrt{2} \rfloor+4 = \lfloor (k+2)\sqrt{2}\rfloor $.

By the standard floor function inequalities, however, we know that $ x-1 < \lfloor x \rfloor < x $ when $ x $ is not an integer. Hence

$ \lfloor k\sqrt{2}\rfloor+4 > k\sqrt{2}+3 > k\sqrt{2}+2\sqrt{2} > \lfloor (k+2)\sqrt{2} \rfloor $,

a contradiction. Hence we have proved both of the desired results. QED.

--------------------

Comment: An interesting result which can be simply generalized to any irrational $ 1 < \alpha < 2 $ and probably any positive irrational $ \alpha $ at all (see if you can prove this). It wasn't hard to reason out that because $ \sqrt{2} < 1.5 $ we really cannot have three integers of the same parity in a row in that sequence. Adding a touch of rigor to the proof turned out to be quite easy as well.

--------------------

Practice Problem: Prove or disprove that, given a positive irrational $ \alpha > 0 $, the sequence $ \lfloor \alpha \rfloor, \lfloor 2\alpha \rfloor, \lfloor 3\alpha \rfloor, \ldots $ contains an infinite number of both even and odd integers.

3 comments:

  1. would this be induction?

    PP: um. duh. like isnt' this obvious? plub in 1 for a and ... POOF !
    u got ur proof.
    haha it rhymes

    ReplyDelete
  2. It's sort of induction. I don't understand what you mean by plug in 1 for a...

    ReplyDelete