第4問

$2^i\times2^i$ のタイルを再帰的に構成する。基本となる $2\times2$ の「左折」タイル $L_1$ は、ねずみが左下のマスに上向きで入り、左下のマスに左向きで出ることを可能にし、$3$ 個のチーズマスを使う；「交差」タイル $X_1$ は、そのような経路2本を交差させることを可能にし、$|L_1|-1=2$ 個のチーズマスを使う。サイズ $2^i\times2^i$ のタイル $L_i,X_i$ が与えられたとき、その4枚（$L_i$ を3枚、$X_i$ を1枚、適切に回転）を $2\times2$ のブロックに配置すると、同じ折れ曲がり・交差の挙動を持つ $2^{i+1}\times2^{i+1}$ のタイル $L_{i+1},X_{i+1}$ が得られ、境界の1マスは二重に数えず共有されるので $|L_{i+1}|=4|L_i|-1$、$|X_i|=|L_i|-1$ となる。