MathLabs

第4题

考虑一个 32×3232\times32 的棋盘。在左下角的方格中放置一只朝上的老鼠,并在其他若干方格中放置奶酪。老鼠开始移动:除非遇到奶酪,否则它一直向前;遇到奶酪时,它吃掉一部分奶酪,向右转,然后继续向前。若在这一过程中老鼠恰好品尝每块奶酪一次,随后从棋盘掉落,则称含有奶酪的方格集合为好集合。证明:(a) 不存在含 888888 个方格的好集合;(b) 存在含至少 666666 个方格的好集合。
第 1/4 步:连续 4 次转弯会闭合成一个环
no 4 consecutive cheese-visits in the move sequence\text{no 4 consecutive cheese-visits in the move sequence}
详细分析

称老鼠踏上的格子为被访问的格子(奶酪格或空格)。若老鼠在四个连续步骤中访问了四个奶酪格,它将在单位步之后连续右转四次,描出一个封闭的单位正方形,回到这一连串开始的格子——但每个奶酪格只被访问一次,矛盾。故被访问格子的序列中不会出现连续四次访问奶酪。