5. Consider a $2008 \times 2008$ chess board. Let $M$ be the smallest number of rectangles that can be drawn on the chess board so that the sides of every cell of the board is contained in the sides of one of the rectangles. Find the value of $M$. (For example, for the $2 \times 3$ chess board, the value of $M$ is 3 .)
5. The answer is $M=2009$. All the horizontal sides can be covered by 1004 pieces of $1 \times 2008$ rectangles except the boundary of the chess board which can be covered by the boundary rectangle. The remaining vertical sides can be covered by 1004 pieces of $2008 \times 1$ rectangles. Thus $M \leq 2009$.
Now suppose that the chess board has been covered by $M$ rectangles in the desired way. Let $a$ of the rectangles have their top and bottom on the top and bottom of the board, $b$ of the rectangles have their top on the top of the board, $c$ of the rectangles have their bottom on the bottom of the board and $d$ of the rectangles have neither their top nor bottom on the top or bottom of the board.
Since there are 2007 internal horizontal lines, we have $b+c+2 d \geq 2007$ Since there are 2009 vertical lines intersecting the top of the board, we have $2 a+2 b \geq 2009$ or $a+b \geq$ 1005. Similarly, $a+c \geq 1005$. Thus $2 a+b+c \geq 2010$. Hence $2(a+b+c+d) \geq$ 4017 i.e., $M=a+b+c+d \geq 2009$.