LV.AMO.2012.11.5 lv
Plaknē doti \(16\) punkti, kas izvietoti kvadrātiska režģa veidā kā parādīts 4.zīm. Taisnstūri sauksim par labu, ja tā virsotnes atrodas režģa punktos, malas ir paralēlas režģa līnijām un nav tā, ka starp taisnstūra virsotnēm ir gan viens no četriem režģa stūriem (punkti \(A, B, C, D\)), gan viens no četriem režģa punktiem, kas atrodas režģa iekšienē (punkti \(M, N, O, P\) ).
Kāds ir lielākais režģa punktu skaits, ko var atzīmēt tā, lai nebūtu laba taisnstūra, kuram visas virsotnes ir atzīmētie punkti?
Atrisinājums
Tas, ka \(10\) punktus var nokrāsot redzams piem. 19.zīmējumā. Atliek pamatot, ka, ja nokrāsosim \(11\) punktus, tad noteikti atradīsies labs taisnstūris ar visām nokrāsotām virsotnēm. Ja ir nokrāsoti \(11\) punkti tad ir divas iespējas:
(A) ir kāda rinda, kur ir nokrāsoti \(4\) punkti,
(B) nav tādas rindas.
(A) gadījumā noteikti vēl ir rinda, kurā ir nokrāsoti vismaz \(3\) punkti, tad no šīm abām rindām noteikti var izvēlēties labu taisnstūri, kuram visas virsotnes ir nokrāsotas (ņemam vai nu divus vidējos, vai malējos punktus (tos, kuri abi ir nokrāsoti) no tās rindas, kur ir \(3\) nokrāsoti punkti un tos pašus no tās rindas, kur ir \(4\)).
(B) gadījumā, ja katrā rindā ir ne vairāk kā \(3\) nokrāsoti punkti, tad ir vismaz \(3\) rindas, kurās ir vismaz \(3\) nokrāsoti punkti. Tātad būs vai nu augšējā un apakšējā, vai divas vidējās rindas ar \(3\) nokrāsotiem punktiem. Tad no šīm divām rindām var izvēlēties labu taisnstūri, kuram visas virsotnes ir nokrāsotas- jāņem tās divas kolonas, kurās abām šīm rindām ir nokrāsoti punkti.
