LV.NOL.2023.10.2 en lv
Uz papīra lapas atzīmēti daži punkti tā, ka nekādi trīs punkti neatrodas uz vienas taisnes. Daži punkti ir savienoti ar nogriežņiem tā, ka no katra punkta iziet tieši \(4\) nogriežņi. Zināms, ka nav uzzīmēts neviens tāds trijstūris, kuram visas virsotnes ir dotajos punktos. Kāds ir mazākais skaits punktu, kas var būt atzīmēti uz papīra lapas?
Atrisinājums
Mazākais iespējamais punktu skaits ir astoņi. Dotajā piemērā (skat. 3.att.) punkti sadalīti divās grupās (1. grupa un 2. grupa) pa četriem punktiem tā, ka katrs pirmās grupas punkts ir savienots ar katru otrās grupas punktu, bet nav savienots ar nevienu savas grupas punktu. Izvēloties jebkurus trīs punktus, vismaz divi būs vienā grupā, tātad attiecīgie punkti nebūs savienoti ar nogriezni, līdz ar to nebūs uzzīmēts neviens trijstūris, kura virsotnes ir dotajos punktos.
Pierādīsim, ka uz lapas nevar būt atzīmēts mazāks skaits punktu. Apskatām punktu \(A\) (skat. 4.att.), kas savienots ar tieši \(4\) citiem punktiem. Apskatām punktu \(B\) (skat. 4.att.). Tā kā nav uzzīmēts neviens trijstūris, tad punkts \(B\) nevar būt savienots ne ar vienu citu punktu, kas savienots ar \(A\), bet tādā gadījumā nepieciešami vēl vismaz \(3\) citi punkti, tas ir, kopā uz lapas ir atzīmēti vismaz \(8\) punkti.