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