LV.AMO.2004.11.5 lv
Komisijā darbojas \(25\) deputāti, daži no tiem draudzējas (ja \(A\) draudzējas ar \(B\), tad arī \(B\) draudzējas ar \(A\)). Katram deputātam ir tieši \(n\) draugi. Ja kādi divi deputāti (apzīmēsim tos ar \(X\) un \(Y\)) nedraudzējas savā starpā, tad noteikti eksistē tāds deputāts, kas draudzējas gan ar \(X\), gan ar \(Y\).
Kāda ir mazākā iespējamā \(n\) vērtība?
Atrisinājums
Atbilde: \(n=6\).
Apskatām deputātu \(A\), visus viņa draugus un visus šo draugu draugus. Saskaņā ar uzdevuma nosacījumiem citu deputātu nav. Tāpēc \(1+n+n(n-1) \geq 25\), no kurienes \(n \geq 5\). Parādīsim, ka \(n=5\) nav iespējams. Augstāk minētajā uzskaitījumā " \(A,\ A\) draugi un \(A\) draugu draugi" tieši viens deputāts būtu uzskaitīts divas reizes. Skaidrs, ka tas var būt tikai " \(A\) drauga draugs", kurš kā tāds uzskaitīts divas reizes. Tāpēc \(A\) pieder tieši vienam ciklam ar garumu \(4\). Tas attiecas uz patvaļīgu \(A\). Bet \(25\) deputāti nevar sadalīties ciklos ar garumu \(4\).
Parādīsim, ka \(n=6\) ir iespējams. Apskatām \(5\) ciklus, katrā pa \(5\) virsotnēm. Apzīmējam patvaļīgus \(2\) ciklus ar
un "nodefinējam" starp tiem draudzības \(A_{1}B_{1},\ A_{2}B_{3},\ A_{3}B_{5},\ A_{4}B_{2},\ A_{5}B_{4}\) (t.i., ja \(A_{i}\) un \(A_{j}\) savā starpā draudzējas, tad viņu draugi ciklā \(B\) savā starpā nedraudzējas un otrādi).
Viegli pārbaudīt, ka uzdevuma nosacījumi ir izpildīti.