Memotong persegi

[Tournament of Towns 1997 Musim Gugur 1997 Junior O Level] Kita ingin menggambar beberapa garis lurus di papan kotak-kotak sehingga setidaknya ada satu garis yang melewati bagian dalam setiap persegi kecil. Tentukan banyaknya garis paling sedikit yang diperlukan untuk papan (a) ; (b) .

Solusi
Kita klaim bahwa satu garis melewati bagian dalam dari paling banyak persegi pada papan kotak-kotak . Perhatikan bahwa ada garis horizontal di dalam papan dan garis vertikal di dalam papan, totalnya ada garis. Setiap kali suatu garis melewati satu kotak ke kotak lain (berpindah), garis itu pasti memotong satu dari garis tadi. Jadi, satu garis paling banyak hanya “berpindah” sebanyak kali. Maka garis itu paling banyak melewati bagian dalam dari persegi. Klaim kita terbukti.

Sekarang, untuk bagian (a), satu garis hanya bisa melewati 5 kotak. Jadi perlu minimum 2 garis. Ini bisa dilakukan seperti ditunjukkan gambar. Untuk bagian (b), satu garis bisa melewati 7 kotak, sehingga kita perlu 3 garis. Ini juga dapat dilakukan, seperti gambar.