MathDB

4

Part of 2021 APMO

Problems(1)

Mouse eating cheese in a square grid

Source: APMO 2021 Problem 4

6/9/2021
Given a 32×3232 \times 32 table, we put a mouse (facing up) at the bottom left cell and a piece of cheese at several other cells. The mouse then starts moving. It moves forward except that when it reaches a piece of cheese, it eats a part of it, turns right, and continues moving forward. We say that a subset of cells containing cheese is good if, during this process, the mouse tastes each piece of cheese exactly once and then falls off the table. Show that:
(a) No good subset consists of 888 cells. (b) There exists a good subset consisting of at least 666 cells.
combinatoricsAPMO