Bài 4
Trong một thị trấn n nhân n, các ngôi nhà được đánh số (i,j), với (1,1) ở góc trên trái. Ban đầu nhà (1,c) cháy, trong đó c không vượt quá n/2. Mỗi khoảng thời gian đơn vị, lính cứu hỏa bảo vệ một nhà chưa cháy, rồi lửa lan tới mọi nhà chưa được bảo vệ kề với các nhà đang cháy ở đầu khoảng. Nhà đã bảo vệ vẫn được bảo vệ. Hỏi nhiều nhất có thể cứu được bao nhiêu nhà? Hai nhà kề nhau khi đúng một tọa độ khác nhau 1.
Bước 4 trên 6: Chặn từng mức bằng quy nạp
Phân tích chi tiết
Chứng minh s(t)≤t−p(t). Điều này rõ ràng khi t=1. Nếu đúng tại t=k, các láng giềng của bất kỳ k−p(k)+1 nhà mức k+1 chứa ít nhất từng ấy nhà mức k, trong khi mức k có nhiều nhất s(k) nhà chưa cháy. Vì vậy nhiều nhất k−p(k) nhà mức k+1 không có láng giềng đang cháy. Tính thêm d(k+1) nhà đã bảo vệ, s(k+1)≤k−p(k)+d(k+1). Bất đẳng thức p(k+1)+d(k+1)≤p(k)+1 ở bước 3 tương đương với k−p(k)+d(k+1)≤(k+1)−p(k+1), hoàn tất bước quy nạp.