Klasē ir \(n\) (\(n\ge 2\)) skolēnu; daži no tiem draudzējas. Ja divi skolēni nedraudzējas savā starpā, tad 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.)
Ir iespējams, ka ir \((n-1)\) draudzība. Piemēram, ja viens skolēns draudzējas ar visiem pārējiem, tad uzdevuma nosacījumi izpildās.
Pierādīsim, ka tas ir mazākais iespējamais draudzību skaits. Ņemsim vienu skolēnu \(A\). Pieņemsim, ka tas draudzējas ar \(B_1, B_2, \ldots, B_k\).
Ja \(k=n-1\), tad draudzību skaits ir ne mazāks par \((n-1)\).
Ja \(k<n-1\), tad katram skolēnam \(X\) no pārējiem \(n-(k+1)\) skolēniem, kas nedraudzējas ar \(A\), jādraudzējas ar kādu no \(B_i\) (tikai šie skolēni var būt tie, kas draudzējas gan ar \(A\), gan ar \(X\)). Tātad pavisam kopā ir ne mazāk par \(k+n-(k+1)=n+1\) draudzībām.