方格感染
Square Infection
题目详情
在一个 的棋盘上，感染按如下规则传播：
- 每个格子只有上下左右 4 个邻居。
- 如果某个格子有至少 2 个被感染的邻居，则该格子也会被感染。
证明：如果初始感染格子数少于 ，则不可能最终感染整张棋盘。
提示：不变量。
An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbors, it becomes infected itself. (Each square has 4 neighbors only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.
Hint
Invariance
解析
考虑“感染区域的周长”（感染格子与非感染格子的边界长度）。
在该传播规则下，感染扩散不会让周长增加：周长保持不变或减少。
若初始感染 个格子，则其周长最多为 。但要感染整张 棋盘，边界周长至少需要达到 。
当 时，，而周长又无法增加，故不可能感染整张棋盘。
Original Explanation
Solution
Perimeter of infected area can't increase. It stays constant or decreases. Initially maximum perimeter is 4 * k if k blocks are infected. But to infect all blocks, the perimeter must increase to 4 * n, . This is not possible