Feladat: Pontversenyen kívüli P.54 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Göndőcs Ferenc ,  Komjáth Péter ,  Lempert László ,  Papp Zoltán ,  Prőhle Tamás ,  Simon Júlia 
Füzet: 1970/szeptember, 27 - 28. oldal  PDF  |  MathML 
Témakör(ök): Összefüggések binomiális együtthatókra, Kombinatorikai leszámolási problémák, Kombinációk, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1970/január: Pontversenyen kívüli P.54

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az azonosságot egy feladat két különböző megoldásával igazoljuk.
Tegyük fel, hogy egy dobozban m pár különböző kesztyű van. Kérdés, hányféleképpen lehet kivenni közülük 2n darabot. Az egyik lehetséges megoldást jól ismerjük:

(2m2n),
ismétlés nélküli kombináció, a másik a következő.
Csoportosítsuk a lehetséges kiválasztásokat aszerint, hogy hány pár kesztyűt érintenek (akár úgy, hogy a pár mindkét darabja, akár csak egyike szerepel a kiválasztásban). Legyen az érintett párok száma k. Ezt a k párt az m pár közül (mk)-féleképpen választhatjuk ki.
Jelölje továbbá x az érintett párok között a teljes párok számát (tehát azokét, melyeknek mindkét darabját kiválasztottuk). Így a félben hagyott párok száma k-x. Mivel 2n db kesztyűt választunk ki, fennáll 2x+(k-x)=2n, és így a teljes párok száma x=2n-k és a páratlan kesztyűk száma k-x=2k-2n.
A k érintett pár közül a teljes párokat(kx)=(k2n-k)-féleképpen választhatjuk ki, és ezután a 2k-2n félpár mindegyikéből egymástól függetlenül választhatjuk a jobb, ill. a bal kesztyűt, vagyis 2-féleképpen választhatunk. Így ha sorban megválasztottuk az érintett párokat, majd ezek közül a teljes párokat, akkor a félpárok tekintetében minden esetben 22k-2n választási lehetőségünk van.
Mivel pedig az érintett párok száma legalább n és legfeljebb 2n, az összes lehetséges kiválasztások számát az (1) bal oldalán álló összeg is megadja. Ez szükségképpen megegyezik első megoldásunk eredményével.
 

Simon Júlia (Győr, Kazinczy F. Gimn., IV. o. t.)