Question from Engel's Problem Solving Strategies: An infinite chessboard consists of $1 \times 1$ squares. A flea starts on a white square and makes jumps by $\alpha$ to the right and $\beta$ upwards, where $\alpha / \beta$ is irrational. Prove that sooner or later it will reach a black square.

WLOG suppose that the flea starts at $(0,0)$. So the flea steps on the coordinates $(k\alpha, k\beta)$, for all $k \in \mathbb{N}$. I need to show that eventually $\lfloor{k\alpha}\rfloor + \lfloor{k \beta}\rfloor$ is an even number.

So I must show that $\lfloor{k\alpha}\rfloor$ and $\lfloor{k \beta}\rfloor$ must eventually have the same parity. Intuitively I know there must exist some $k$ such that $\lfloor k\alpha \rfloor$ and $\lfloor (k+1) \alpha \rfloor$ have same parity, while $\lfloor k\beta \rfloor$ and $\lfloor (k+1)\beta \rfloor$ have different parity.

How do I do this?

  • $\begingroup$ 1. Do you mean an odd number rather than an even number? 2. I notice that the question doesn't say where in the white square the flea starts (in the middle? near a corner?) so the floor operation might not correspond accurately to the flea's position. $\endgroup$ – Rosie F May 11 '19 at 7:11
  • $\begingroup$ I think WLOG we can assume that the square with bottom left coordinate being (0,0) is white $\endgroup$ – eatfood May 11 '19 at 8:16
  • $\begingroup$ Doesn't seem all that textbook-y to me. VTO. $\endgroup$ – Bass May 11 '19 at 20:12

Browse other questions tagged or ask your own question.