MathLabs

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 5 trên 6: Tính cận trên
Bước trướcBước tiếp
∑t=1n−1s(t)≤∑t=1n−1t,∣{ℓ>n−1}∣=n2−n(n−1)2−c(n−c+1)\sum_{t=1}^{n-1}s(t)\le\sum_{t=1}^{n-1}t,\quad |\{\ell>n-1\}|=n^2-\frac{n(n-1)}2-c(n-c+1)
Phân tích chi tiết

Vì vậy ở các mức không quá n−1 cứu được nhiều nhất tổng 1 đến n−1 nhà. Đếm trực tiếp các điểm lưới trên các mức đó được n(n−1)/2+c(n−c+1); các mức còn lại chứa n bình phương trừ số này nhà.