LV.NOL.2009.9.5 lv
Pieņemsim, ka \(n \geqq 3\), \(n\) - naturāls skaitlis. Aplūkosim patvaļīgu \(n\) cilvēku grupu.
(A) pierādīt, ka šajā grupā var atrast divus tādus cilvēkus \(A\) un \(B\), kam starp pārējiem ir vienādi paziņu daudzumi,
(B) rūķītis Muriburis apgalvo: katriem diviem šīs grupas cilvēkiem \(A\) un \(B\), kam šajā grupā paziņu daudzumi ir vienādi, var atrast vai nu tādu cilvēku \(C\), kas pazīst gan \(A\), gan \(B\), vai arī tādu cilvēku \(D\), kas nepazīst ne \(A\), ne \(B\). Vai Muriburis runā patiesību, ja \(n=4\)? Bet ja \(n=2009\)?
\(\underline{Piezīme:}\) uzskatām, ka neviens nepazīst pats sevi un, ja \(X\) pazīst \(Y\), tad arī \(Y\) pazīst \(X\).
Atrisinājums
(A) Pieņemsim pretējo, ka tādu divu cilvēku nav. Tā kā cilvēku ir tieši \(n\) un paziņu daudzums vienam cilvēkam var būt \(0;\ 1;\ 2;\ \ldots;\ n-1\) (t.i., tieši \(n\) dažādas vērtības), tad katrai šai vērtībai "jārealizējas"; t.sk. jārealizējas arī paziņu daudzumiem \(0\) un \(n-1\). Bet tas nav iespējams: ja ir kāds, kam nav neviena paziņas, tad nevar būt neviena, kas pazīst visus \(n-1\) citus. Iegūta pretruna.
(B) Pie \(n=4\) var gadīties, ka trešā cilvēka nav: skat, piem., 7.zīm., kur punkti attēlo cilvēkus, bet līnijas - pazīšanās.
Pie \(n=2009\) tādi cilvēki noteikti atradīsies. Pieņemsim pretējo: nekādiem diviem cilvēkiem ar vienādiem paziņu daudzumiem minētā trešā cilvēka nav. Ņemsim divus cilvēkus \(A\) un \(B\) ar vienādiem paziņu daudzumiem (tādi eksistē saskaņā ar (A) punktu). Katru no pārējiem \(n-2\) cilvēkiem pazīst \(\underline{tieši\ viens}\) no \(A\) un \(B\), tāpēc \(n-2\) jādalās ar \(2\) (citādi \(A\) un \(B\) paziņu daudzumi neiznāktu vienādi). Tāpēc \(n\) jābūt pāra skaitlim. Bet \(2009\) ir nepāra.