MathLabs

第4题

考虑一个 32×3232\times32 的棋盘。在左下角的方格中放置一只朝上的老鼠，并在其他若干方格中放置奶酪。老鼠开始移动：除非遇到奶酪，否则它一直向前；遇到奶酪时，它吃掉一部分奶酪，向右转，然后继续向前。若在这一过程中老鼠恰好品尝每块奶酪一次，随后从棋盘掉落，则称含有奶酪的方格集合为好集合。证明：(a) 不存在含 888888 个方格的好集合；(b) 存在含至少 666666 个方格的好集合。
第 4/4 步：迭代五次达到规模 32
上一步下一步
∣L1∣=3, ∣L2∣=11, ∣L3∣=43, ∣L4∣=171, ∣L5∣=683≥666|L_1|=3,\ |L_2|=11,\ |L_3|=43,\ |L_4|=171,\ |L_5|=683\ge666
详细分析

由于 32=2532=2^5，从 ∣L1∣=3|L_1|=3 出发应用四次递推得 ∣L2∣=4⋅3−1=11|L_2|=4\cdot3-1=11，∣L3∣=4⋅11−1=43|L_3|=4\cdot11-1=43，∣L4∣=4⋅43−1=171|L_4|=4\cdot43-1=171，∣L5∣=4⋅171−1=683|L_5|=4\cdot171-1=683。瓷砖 L5L_5 是一个 32×3232\times32 的排列，老鼠从左下角格子朝上进入，其奶酪格构成一个至少含 683≥666683\ge666 个格子的好子集。