Sākums

LV.AMO.2022A.9.5

Kāds mazākais skaits rūtiņu jāaizkrāso taisnstūrī ar izmēriem \(8 \times 8\) rūtiņas, lai nevarētu atrast nevienu taisnstūri ar izmēriem \(1 \times 5\) rūtiņas (kurš var būt novietots gan horizontāli, gan vertikāli), kuram visas rūtiņas ir neaizkrāsotas?

Noslēpt atrisinājumu

Atrisinājums

Mazākais skaits rūtiņu, kas jāaizkrāso, ir \(12\), skat., piemēram, 12.att.

Pamatosim, ka, atbilstoši uzdevuma nosacījumiem, mazāk kā \(12\) rūtiņas nav iesējams aizkrāsot. Skaidrs, ka katrā no 13.att. redzamajiem \(12\) ar treknāku līniju izceltajiem taisnstūriem jābūt aizkrāsotai vismaz vienai rūtiņai. Tātad jāaizkrāso vismaz \(12\) rūtiņas.