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 3 of 4: Part (b): a recursive family of tiles

Previous step Next step

|L_1|=3,\quad |X_i|=|L_i|-1,\quad |L_{i+1}|=4|L_i|-1

Detailed analysis

Build $2^i\times2^i$ tiles recursively. A base $2\times2$ "turn-left" tile $L_1$ lets the mouse enter at the bottom-left cell facing up and leave at the bottom-left cell facing left, using $3$ cheese-cells; a "cross" tile $X_1$ lets two such paths cross using $|L_1|-1=2$ cheese-cells. Given tiles $L_i,X_i$ of size $2^i\times2^i$ , arranging four of them (three copies of $L_i$ and one of $X_i$ , suitably rotated) in a $2\times2$ block produces $2^{i+1}\times2^{i+1}$ tiles $L_{i+1},X_{i+1}$ with the same turning/crossing behavior, where one boundary cell is shared rather than double-counted, giving $|L_{i+1}|=4|L_i|-1$ and $|X_i|=|L_i|-1$ .