Dừng câu đố Coronavirus [đã đóng]

Question

Một vùng hình vuông $2020 \times 2020 \text{ km}^2$ chia thành $2020^2$tế bào. Một số tế bào bị ô nhiễm bởi covid-19 . Mỗi tuần, vi rút lây lan đến những tế bào có ít nhất$2$điểm chung với các tế bào bị ô nhiễm. Tìm số lượng tế bào bị ô nhiễm tối đa sao cho bất kể chúng nằm ở đâu, đại dịch covid-19 sẽ không lây lan ra toàn bộ khu vực.

Bạn học của tôi đã đưa cho tôi bài toán này (tốt hơn là một câu đố) có thể là trong thời gian khóa (tháng 7-8) nhưng tôi đã quên nó và hôm qua anh ấy hỏi tôi rằng liệu tôi có thể giải được bài toán hay không? Và sau đó câu trả lời rõ ràng là không, mặc dù tôi đã nỗ lực hết sức để giải quyết vấn đề lần đó và sau cuộc họp ngày hôm qua và cả ngày hôm nay tôi đã dành rất nhiều thời gian nhưng không thể tìm ra. Cảm ơn đã quan tâm!

Answer 1

Yêu cầu: Trên một $n$ bởi $n$ lưới, nếu có ít hơn $n$ hình vuông bị nhiễm ban đầu, sau đó nhiễm trùng sẽ không lan rộng ra toàn bộ khu vực.

Xác định một cạnh của hình vuông là cạnh biên nếu một cạnh của cạnh bị nhiễm nhưng cạnh còn lại không bị nhiễm. (Khu vực bên ngoài toàn bộ$n$ bởi $n$ lưới điện được coi là luôn không bị ô nhiễm.)

Bổ đề chính: Khi sự lây nhiễm lan truyền, số lượng các cạnh biên giới không bao giờ có thể tăng lên.

Chứng minh bổ đề then chốt: Bất cứ khi nào sự lây lan sang một ô vuông mới, thì ít nhất hai trong số những người hàng xóm của nó đã bị nhiễm, do đó bạn mất ít nhất hai cạnh biên và thu được nhiều nhất hai. Kết thúc bằng chứng.

Bằng chứng xác nhận quyền sở hữu: Giả sử sự lây nhiễm lan rộng ra toàn bộ khu vực. Khi đó, số cạnh biên là$4n$(toàn bộ mép ngoài của tấm ván). Theo bổ đề chính, số lượng các cạnh biên giới ban đầu phải ít nhất là$4n$. Do đó, ít nhất phải có$n$hình vuông ban đầu bị nhiễm. Nói cách khác, nếu có ít hơn$n$ hình vuông bị nhiễm ban đầu, sau đó sự lây nhiễm sẽ không lây lan ra toàn bộ khu vực.

(Nhân tiện, có nhiều cấu hình ban đầu về kích thước $n$ dẫn đến toàn bộ bảng bị nhiễm trùng, không chỉ các đường chéo.)