Sākums

LV.SOL.2004.8.4   lv

Kādā klasē ir \(25\) skolēni. Sauksim skolēnu par noslēgtu, ja viņam klasē nav vairāk par \(20\) draugiem. Pierādīt: klasē ir vai nu divi noslēgti skolēni, kas savā starpā nedraudzējas, vai arī divi draugi, neviens no kuriem nav noslēgts, vai arī abu minēto veidu skolēnu pāri (uzskatām: ja \(A\) draudzējas ar \(B\), tad arī \(B\) draudzējas ar \(A\)).

Hide solution

Atrisinājums

Sāksim skolēnu, kas nav noslēgts, par atklātu. Pieņemsim pretējo tam, kas jāpierāda. Ja visi skolēni ir noslēgti, tad tie visi savā starpā draudzējas – pretruna, jo katram ir \(24\) draugi. Pieņemsim, ka ir kāds atklāts skolnieks \(A\). Apskatām viņa draugus; to ir vismaz \(21\), un tie visi ir noslēgti. Tāpēc tie visi draudzējas savā starpā. Tāpēc katram no tiem ir vismaz \(21\) draugs (pārējie \(20\) un \(A\)), un viņi ir atklāti – pretruna.