Problem 4

Consider a

32\times32

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

888

cells; (b) there exists a good subset consisting of at least

666

cells.

Step 2 of 4: Part (a): counting forces too many cells

Previous step Next step

888=3\cdot296\ \Rightarrow\ \ge296\text{ blocks},\ \ge295\text{ separators},\ \ge148\text{ gap-cells};\quad 888+148>32^2

Detailed analysis

Suppose a good subset has $888$ cheese-cells. By the previous step, blocks of consecutive cheese-visits have length at most $3$ , so at least $\lceil888/3\rceil=296$ blocks are needed, requiring at least $295$ separating gap-visits between them. Each gap-cell is visited at most twice (once moving vertically, once horizontally), so at least $\lceil295/2\rceil=148$ distinct gap-cells are needed. The board then needs at least $888+148=1036>32^2=1024$ cells, a contradiction. Hence no good subset has $888$ cells.