第4题
在一个 n×n 的小镇中,房屋编号为 (i,j),左上角为 (1,1)。时刻 0 房屋 (1,c) 起火,其中 c≤n/2。每个单位时间内,消防员保护一座尚未着火的房屋,随后火焰从时间段开始时着火的每座房屋蔓延到所有未保护的相邻房屋;已保护房屋始终受保护。最多能救下多少座房屋? 相邻指恰有一个坐标相差 1。
详细分析证明 s(t)≤t−p(t)。t=1 时显然。假设 t=k 时成立。第 k+1 层任取 k−p(k)+1 座房屋,其邻居在第 k 层至少包含同样多的房屋,而第 k 层未着火的至多为 s(k) 座。因此第 k+1 层没有着火邻居的至多为 k−p(k) 座。计入 d(k+1) 座已保护房屋,s(k+1)≤k−p(k)+d(k+1)。第三步的记账不等式 p(k+1)+d(k+1)≤p(k)+1 等价于 k−p(k)+d(k+1)≤(k+1)−p(k+1),从而完成归纳。