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.
Problem
Source: Middle European Mathematical Olympiad T-3
Tags: geometry, rectangle, combinatorics proposed, combinatorics
12.09.2017 18:28
No response for three years. I have found a solution in https://skmo.sk/dokumenty.php. But this is written in Slovak, can someone help to translate it into English?
Attachments:

09.04.2020 23:39
We use the chessboard coloring, letting the lower left and the upper right corners be black. The main idea is simply that the corner in which the ant is always changes its color. So to go from LL to UR it passes through a odd number of squares, implying that a MEMOrable rectangle must have odd area, and odd sides. Now we prove that the LL, UR of a MEMOrable rectangle are white. Indeed, suppose otherwise, i.e., they're both black. Then let's count the number of black squares in the board, which is equal to the number of white squares. But a walk from the major LL to the major UR contains more black than white, and so does this MEMOrable rectangle, a contradiction. We have characterized all MEMOrable rectangles: lets consider the major LL to be $(1,1)$ and the major UR to be $(K,L)$. Let $A=\{(2a, 2b+1) \ \text{in the grid}\}$ and $B=\{(2a+1, 2b) \ \text{in the grid}\}.$ So a rectangle is MEMOrable iff all its vertices are in only one of $A$ and $B$. Now we just have to count them. Clearly $A$ and $B$ form rectangles $K \times L.$ In such a rectangle, the number of rectangles inside it is: $$\binom{k}{2}\binom{l}{2} \ \text{(choose two distinct columns and two distinct rows)}$$$$+ \binom{k}{2}l \ \text{(choose one row and two distinct columns)}$$$$+\binom{l}{2}k \ \text{(choose one column and two different rows)}$$$$+kl \ \text{(a single square)}$$which equals $\frac{kl(k+1)(l+1)}{4}$, so the total is two times it, namely $\frac{kl(k+1)(l+1)}{2}.$