Menghentikan teka-teki Coronavirus [ditutup]

Question

Wilayah persegi $2020 \times 2020 \text{ km}^2$ dibagi menjadi $2020^2$sel. Beberapa sel terkontaminasi oleh Covid-19 . Setiap minggu virus menyebar ke sel yang paling sedikit$2$sisi yang sama dengan sel yang terkontaminasi. Temukan jumlah maksimum sel yang terkontaminasi sehingga di mana pun mereka berada, pandemi Covid-19 tidak akan menyebar ke seluruh wilayah.

Teman sekolah saya memberi saya masalah ini (lebih baik mengatakan teka-teki) mungkin selama periode kuncian (Juli-Agustus) tetapi saya lupa dan kemarin dia bertanya apakah saya sudah bisa menyelesaikan masalah atau tidak? Dan kemudian jawabannya jelas tidak, meskipun saya berusaha cukup keras di balik masalah waktu itu dan setelah pertemuan kemarin dan juga hari ini saya memberikan banyak waktu tetapi tidak dapat memahaminya. Terima kasih atas perhatiannya!

Answer 1

Klaim: Di $n$ oleh $n$ grid, jika lebih sedikit dari $n$ kotak yang awalnya terinfeksi, kemudian infeksi tidak akan menyebar ke seluruh wilayah.

Tentukan tepi sebuah bujur sangkar sebagai tepi perbatasan jika salah satu sisi tepi terinfeksi tetapi sisi lainnya tidak terinfeksi. (Wilayah di luar keseluruhan$n$ oleh $n$ grid dianggap selalu tidak terinfeksi.)

Lemma kunci: Saat infeksi menyebar, jumlah tepi perbatasan tidak akan pernah meningkat.

Bukti kunci utama: Setiap kali infeksi menyebar ke alun-alun baru, maka setidaknya dua tetangganya sudah terinfeksi, oleh karena itu Anda kehilangan setidaknya dua tepi perbatasan dan mendapatkan paling banyak dua. Akhir pembuktian.

Bukti klaim: Misalkan infeksi menyebar ke seluruh wilayah. Pada saat itu, jumlah tepi perbatasan adalah$4n$(seluruh tepi luar papan). Menurut lemma kunci, jumlah tepi perbatasan awal setidaknya harus$4n$. Oleh karena itu, setidaknya harus ada$n$kotak awal terinfeksi. Dengan kata lain, jika jumlahnya lebih sedikit dari$n$ kotak yang awalnya terinfeksi, kemudian infeksi tidak akan menyebar ke seluruh wilayah.

(Ngomong-ngomong, ada banyak konfigurasi awal ukuran $n$ yang menyebabkan seluruh papan terinfeksi, bukan hanya diagonal.)