Problem 4
Consider a table. We put a mouse (facing up) in the bottom-left cell and pieces of cheese in 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. A subset of cells containing cheese is called 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 cells; (b) there exists a good subset consisting of at least cells.
Step 1 of 4: A run of 4 turns would close a loop
Detailed analysis
Call a cell visited if the mouse steps onto it (a cheese-cell or a gap-cell). If the mouse visited four cheese-cells at four consecutive steps, it would turn right four times in a row after unit moves, tracing a closed unit square and returning to the cell where this run started — but every cheese-cell is visited only once, a contradiction. So the sequence of visited cells never contains four consecutive cheese-visits.