Sākums

LV.SOL.1994.11.5   lv

Klasē ir \(n\) (\(n \ge 4\)) skolēnu; daži no tiem draudzējas. Ja divi skolēni nedraudzējas savā starpā, tad klasē var atrast vismaz \(2\) citus skolēnus kas draudzējas ar tiem abiem.

Kāds ir mazākais iespējamais draudzību skaits?

(Uzskatām, ka katrs draugu pāris veido vienu draudzību, pārus \(AB\) un \(BA\) uzskatām par vienu un to pašu pāri.)

Hide solution

Atrisinājums

Attēlosim skolēnus ar punktiem, bet draudzēšanos ar līnijām. Kā redzams \(20.\) zīm., meklējamais skaits var būt \(2n-4\).

\(20.\) zīm.

Viegli saprast, ka katrs skolēns draudzējas vismaz ar \(2\) citiem. Ja katrs draudzētos vismaz ar \(4\) citiem, tad draudzību skaits būtu ne mazāks par \(\frac{4n}{2}=2n\).

Ja ir skolēns \(X\), kas draudzējas tikai ar diviem citiem (teiksim, ar \(A\) un \(B\)). tad \(A\) un \(B\) ir vienīgie, kas var sasaistīt \(X\) ar katru no \((n-3)\) atlikušajiem skolēniem; tāpēc draudzību nav mazāk par \(2+2(n-3)=2n-4\).

Līdzīgi gadījumā, ja \(X\) draudzējas ar \(3\) citiem skolēniem \(A\), \(B\), \(C\), draudzību nav mazāk par \(3+2(n-4)=2n-5\). Tomēr draudzību skaits varētu nepārsniegt \(2n-5\) tikai tad, ja \(n-4\) pārējie skolēni savā starpā nedraudzējas un ar katru no viņiem draudzējas tieši \(2\) no skolēniem \(A\), \(B\), \(C\). Pieņemsim, ka ir skolēns \(R\), ar kuru draudzējas \(A\) un \(B\), un skolēns \(S\), ar kuru draudzējas \(B\) un \(C\). Tad priekš \(R\) un \(S\) nav uzdevumā minēto divu kopīgo draugu. Tāpēc visi \(n-4\) "pārējie" skolēni draudzējas ar vieniem un tiem pašiem diviem no \(A\), \(B\), \(C\). Bet tādā gadījumā atlikušajam no šiem trim skolēniem ir tikai viens draugs; tā ir pretruna.