MathDB

We consider tilings of a rectangular m \times n-board with 1\times2-tiles. The tiles can be placed either horizontally, or vertically, but they aren't allowed to overlap and to be placed partially outside of the board. All squares on theboard must be covered by a tile. (a) Prove that for every tiling of a 4 \times 2010-board with 1\times2-tiles there is a straight line cutting the board into two pieces such that every tile completely lies within one of the pieces. (b) Prove that there exists a tiling of a 5 \times 2010-board with 1\times 2-tiles such that there is no straight line cutting the board into two pieces such that every tile completely lies within one of the pieces.

Problem Statement