Sākums

LV.SOL.2009.12.5   lv

Klasē ir \(z\) zēni un \(m\) meitenes. Katriem diviem zēniem var atrast meiteni, kas vienam no viņiem patīk, bet otram nepatīk. Pierādīt, ka \(2^m \ge z\).

Hide solution

Atrisinājums

Katram zēnam piekārtosim to meiteņu kopu, kas viņam patīk. Tad visas šīs kopas ir dažādas. Tātad meiteņu kopas apakškopu nevar būt mazāk nekā zēnu. Kopai ar \(m\) elementiem ir \(2^m\) apakškopu. Tāpēc \(2^m \ge z\), k.b.j.