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 4 of 4: Iterate five times to size 32

Previous step Next step

|L_1|=3,\ |L_2|=11,\ |L_3|=43,\ |L_4|=171,\ |L_5|=683\ge666

Detailed analysis

Since $32=2^5$ , applying the recursion four times from $|L_1|=3$ gives $|L_2|=4\cdot3-1=11$ , $|L_3|=4\cdot11-1=43$ , $|L_4|=4\cdot43-1=171$ , $|L_5|=4\cdot171-1=683$ . The tile $L_5$ is a $32\times32$ arrangement in which the mouse enters at the bottom-left cell facing up, and its cheese-cells form a good subset of $683\ge666$ cells.