LV.NOL.2007.11.2 lv
Kādā klasē ir \(n\) zēni un \(n\) meitenes. Katrai meitenei patīk \(x\) zēni. Katram zēnam patīk \(y\) meitenes. Pierādīt, ka:
(A) ja \(x+y>n\), tad noteikti var atrast tādu zēnu un tādu meiteni, kas patīk viens otram,
(B) ja \(x+y \leq n\), tad var gadīties, ka šādu zēnu un meiteni atrast neizdodas.
Atrisinājums
(A) Pieņemsim, ka tāda pāra nav. Lūgsim katram zēnam uzrakstīt \(y\) dažādas kartītes - katru ar savu vārdu un kādu tās meitenes vārdu, kas viņam patīk. Līdzīgu darbu lūgsim izdarīt meitenēm. Tā kā savstarpēju simpātiju nav, tad nav divu kartīšu, uz kurām būtu vienādi uzraksti; tāpēc kartīšu nav vairāk par \(n \cdot n=n^{2}\). No otras puses, kartīšu ir \(x \cdot n+y \cdot n=(x+y) \cdot n>n \cdot n=n^{2}\) - pretruna.
(B) Attēlosim meitenes ar punktiem riņķa līnijas iekšpusē, bet zēnus - ar punktiem riņķa linijas ārpusē (skat. 5.zīm., kur \(n=9\)).
Ja katrai meitenei patīk \(x\) zēni pulksteņa rādītāja kustības virzienā, sākot ar to, kurš stāv viņai blakus, bet katram zēnam - \(y\) meitenes pulksteņa rādītāja kustības virzienā, sākot ar to, kura stāv viņam vienu pozīciju priekšā, tad savstarpēju simpātiju nav.