Feladat: Gy.3048 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bárány Kristóf ,  Barát Anna ,  Bérczi Gergely ,  Borsodi Rita ,  Braun Gábor ,  Bujdosó Attila ,  Czirok Levente ,  Davidovics Gábor ,  Devecsery András ,  Frenkel Péter ,  Gyenes Zoltán ,  Hangya Balázs ,  Jeszenszky Gyula ,  Juhász András ,  Kormos Márton ,  Kutalik Péter ,  Kutalik Zoltán ,  Lippner Gábor ,  Méder Áron ,  Mile Veronika ,  Nagy Endre ,  Naszódi Anna ,  Naszódi Gergely ,  Naszvadi Péter ,  Nyul Gábor ,  Páles Csaba ,  Pap Júlia ,  Papp Ágnes ,  Pintér Dömötör ,  Reviczky Ágnes ,  Rudolf Gábor ,  Salamon Éva ,  Sipos András ,  Szabó Jácint ,  Szabó Péter ,  Terék Zsolt ,  Terpai Tamás ,  Tóth Ádám ,  Tótin Ágnes ,  Vaik Zsuzsanna ,  Várkonyi Péter ,  Übelhart István ,  Zábrádi Gergely ,  Zakariás Ildikó ,  Zubcsek Péter Pál 
Füzet: 1996/december, 521 - 522. oldal  PDF  |  MathML 
Témakör(ök): Kombinációk, Kombinatorikai leszámolási problémák, Oszthatósági feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1996/március: Gy.3048

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.

a) Állítsuk először az embereket kettes oszlopba. Az első sor bal oldali helyére 2n ember közül választhatunk, a jobb oldali helyre 2n-1 közül, a második sor bal oldalára 2n-2 közül és így tovább. Ez összesen (2n)! lehetőség. Ezzel azonban minden párosítást többször is számoltunk: a pároknál ugyanis nem számít, ki áll a bal és ki a jobb oldalon, másfelől az sem érdekes, hogy az adott pár hányadik sorban áll. Egy adott párosításból a sorok megkülönböztetésével n! felállást kapunk, ám még ekkor sem vettük figyelembe a jobb és bal oldali helyeket. Ez minden párnál 2 további lehetőség, azaz összesen 2n. Tehát egy párosításból 2n⋅n!-féle kettes oszlopba állítást kapunk, azaz a párosítások száma

(2n)!2n⋅n!.

b) Határozzuk meg először azt, hányféleképpen osztható nk ember k fős csoportokba. Az előző feladatrésznél már látott módszert követjük: a k-as oszlopba állítások számát elosztjuk annyival, ahányféle k-as oszlopba állítás kapható egy k-as csoportba osztásból.
Mivel a csopoton belüli hely nem számít, ez k⋅(k-1)⋅...⋅2⋅1≥1=k! lehetőség csoportonként, azaz összesen (k!)n. Ezen felül még a csoportok sorrendje is mindegy, ami további n! lehetőséget jelent, vagyis összesítve (k!)n⋅n!. A k-as oszlopba állítások száma pedig a) részhez hasonló módon (nk)!; így a csoportba osztásoké
(nk)!(k!)n⋅n!.(1)

Ez tehát egész szám, valamint egész a k és n felcserélésével kapott (nk)!(n!)kk!, s így szorzatuk is:
((nk)!)2(k!)nn!(n!)kk!=((nk)!)2(k!)n+1⋅(n!)k+1,
és éppen ezt kellett igazolnunk.
 Bérczi Gergely (Szeged, Ságvári E. Gimn., II. o.t.) dolgozata alapján

 
Megjegyzés. Az a) feladatrésznél természetes feltevés, hogy n pozitív egészt jelöl, s ezt alkalmaztuk aztán a b) részre is. Amennyiben ott a nullát is megengednénk, az állítás nem marad igaz: ha n=0 és k≥2, akkor megállapodás szerint ((nk!)2=(0!)2=1, (n!)k+1=1, (k!)n+1=k!>1, és így az oszthatóság nem teljesül. Mivel valóban nem volt külön kikötve, jelenthet-e n és k nullát is, így aki ezzel a feltevéssel oldotta meg a feladatot, szintén maximális pontot kapott (amennyiben persze helyes és hiánytalan volt a megoldása.)
Nézzük azért meg, hol romlik el az n=0 esetben a megoldásuk! Az (1) kifejezés értéke n=0 mellett 1(k!)0⋅0!=1, az n és k szerepét felcserélve pedig 11n⋅n!, holott nulla embert nullaféleképpen lehet csoportokba osztani. A másik kifejezés pedig láthatóan még csak nem is egész szám, s ez okozza a problémát.