MathLabs

第4题

考虑一个 32×3232\times32 的棋盘。在左下角的方格中放置一只朝上的老鼠，并在其他若干方格中放置奶酪。老鼠开始移动：除非遇到奶酪，否则它一直向前；遇到奶酪时，它吃掉一部分奶酪，向右转，然后继续向前。若在这一过程中老鼠恰好品尝每块奶酪一次，随后从棋盘掉落，则称含有奶酪的方格集合为好集合。证明：(a) 不存在含 888888 个方格的好集合；(b) 存在含至少 666666 个方格的好集合。
第 2/4 步：(a): 计数迫使格子数过多
上一步下一步
888=3⋅296 ⇒ ≥296 blocks, ≥295 separators, ≥148 gap-cells;888+148>322888=3\cdot296\ \Rightarrow\ \ge296\text{ blocks},\ \ge295\text{ separators},\ \ge148\text{ gap-cells};\quad 888+148>32^2
详细分析

设某个好子集有 888888 个奶酪格。由上一步，连续访问奶酪的每个区块长度至多为 33，故至少需要 ⌈888/3⌉=296\lceil888/3\rceil=296 个区块，从而它们之间至少需要 295295 次空格访问作为分隔。每个空格至多被访问两次，故至少需要 ⌈295/2⌉=148\lceil295/2\rceil=148 个不同的空格。于是棋盘至少需要 888+148=1036>322=1024888+148=1036>32^2=1024 个格子，矛盾。因此不存在由 888888 个格子组成的好子集。