第4問
n×n の町の家を (i,j) で番号付けし、(1,1) を左上とする。時刻0に (1,c) が燃え、c≤n/2 とする。各単位時間に消防士はまだ燃えていない家を1軒守り、その後、区間開始時に燃えていた各家から、守られていない隣接家へ火が広がる。守った家は常に守られる。救える家の最大数を求めよ。隣接とは、一方の座標だけが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)。第3段階の p(k+1)+d(k+1)≤p(k)+1 は k−p(k)+d(k+1)≤(k+1)−p(k+1) と同値なので、帰納法が完了する。