Sākums

LV.SOL.1994.12.5   lv

Klasē ir \(n\) (\(n \ge 4\)) skolēnu; daži no tiem draudzējas. Katriem diviem skolēniem var atrast trešo, 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

Kā redzams \(21\). zīm., draudzību skaits var būt \(n-1+\left[\dfrac{n}{2}\right]\).

\(n=2k\)

\(n=2k+1\)

  1. zīm.

Šķirojam divas iespējas.

1) Ja katrs skolēns draudzējas ar vismaz \(3\) citiem, tad draudzību skaits nav mazāks par

\[ \frac{3n}{2}>n-1+\left[\frac{n}{2}\right]. \]

2) Eksistē tāds skolēns \(A\), kas draudzējas tikai ar diviem citiem \(B\) un \(C\). Tad \(B\) draudzējas ar \(C\) (lai apkalpotu pārus \(AB\) un \(AC\)). Katram no pārējiem skolēniem jādraudzējas vai nu ar \(B\), vai \(C\) (lai būtu apkalpots pāris \(AX\)). Atzīmēsim katram no pārējiem skolēniem vienu minēto draudzību ar \(B\) vai \(C\). Lai apkalpotu pārus \(BX\) un \(CX\), katram no pārējiem (bez \(A\), \(B\), \(C\)) jābūt vēl vienai draudzībai; to skaits nav mazāks par \(\frac{n-3}{2}\), t.i., nav mazāks par \(\left[\frac{n-2}{2}\right]\). Kopā draudzību nav mazāk par

\[ 3+(n-3)+\left[\frac{n-2}{2}\right]=n-1+\left[\frac{n}{2}\right]. \]