MathLabs

第4题

考虑一个 32×3232\times32 的棋盘。在左下角的方格中放置一只朝上的老鼠，并在其他若干方格中放置奶酪。老鼠开始移动：除非遇到奶酪，否则它一直向前；遇到奶酪时，它吃掉一部分奶酪，向右转，然后继续向前。若在这一过程中老鼠恰好品尝每块奶酪一次，随后从棋盘掉落，则称含有奶酪的方格集合为好集合。证明：(a) 不存在含 888888 个方格的好集合；(b) 存在含至少 666666 个方格的好集合。
第 3/4 步：(b): 递归瓷砖族
上一步下一步
∣L1∣=3,∣Xi∣=∣Li∣−1,∣Li+1∣=4∣Li∣−1|L_1|=3,\quad |X_i|=|L_i|-1,\quad |L_{i+1}|=4|L_i|-1
详细分析

递归地构造 2i×2i2^i\times2^i 的瓷砖。基本的 2×22\times2“左转”瓷砖 L1L_1 让老鼠从左下角格子朝上进入，从左下角格子朝左离开，用了 33 个奶酪格；“交叉”瓷砖 X1X_1 让两条这样的路径交叉，用了 ∣L1∣−1=2|L_1|-1=2 个奶酪格。给定尺寸为 2i×2i2^i\times2^i 的瓷砖 Li,XiL_i,X_i，将四块（三块 LiL_i 与一块 XiX_i，适当旋转）排成 2×22\times2 的方块，即得到尺寸为 2i+1×2i+12^{i+1}\times2^{i+1}、具有相同转弯/交叉行为的瓷砖 Li+1,Xi+1L_{i+1},X_{i+1}，其中一个边界格被共用而非重复计数，于是 ∣Li+1∣=4∣Li∣−1|L_{i+1}|=4|L_i|-1，∣Xi∣=∣Li∣−1|X_i|=|L_i|-1。