Problem

Source: Middle European Mathematical Olympiad T-3

Tags: geometry, rectangle, combinatorics proposed, combinatorics



Let $K$ and $L$ be positive integers. On a board consisting of $2K \times 2L$ unit squares an ant starts in the lower left corner square and walks to the upper right corner square. In each step it goes horizontally or vertically to a neighbouring square. It never visits a square twice. At the end some squares may remain unvisited. In some cases the collection of all unvisited squares forms a single rectangle. In such cases, we call this rectangle MEMOrable. Determine the number of different MEMOrable rectangles. Remark: Rectangles are different unless they consist of exactly the same squares.