Feladat: Gy.3279 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bálint Gergely ,  Győri Nikolett ,  Harangi Viktor ,  Kovács Erika Renáta ,  Kunszenti-Kovács Dávid ,  Máthé András ,  Siska Ádám ,  Somogyi Dávid 
Füzet: 2000/január, 21 - 23. oldal  PDF file
Témakör(ök): Kombinatorikai leszámolási problémák, Gyakorlat
Hivatkozás(ok):Feladatok: 1999/május: Gy.3279

Tíz gyerek ,,bogozódós'' játékot játszik: körbe állnak, és csukott szemmel, kinyújtott kézzel elindulnak a kör közepe felé. Mindenki mindkét kezével megfogja valaki másnak a kezét. Ezután kinyitják a szemüket, és elkezdenek ,,kibogozódni'': átbújnak egymás keze alatt, átlépik egymás kezét stb. (mindenki kellően hajlékony) ‐ de nem engedik el közben egymás kezét. Az összes eset hány százalékában igaz, hogy ha egy helyen két szomszédos gyerek elengedi egymás kezét, akkor a tíz gyerek egymás kezét fogva összefüggő láncot alkot? (H)

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 utolsó mondat feltétele azt jelenti, hogy a 10 gyerek egyetlen ,,kört'' alkotott, mielőtt ketten elengedték egymás kezét. A bonyolult megfogalmazás annak köszönhető, hogy ezen a körön csomó, önátmetszés is lehetséges. Nevezzük mindenesetre ,,körnek'' a feltételnek eleget tevő, esetleg csomót is tartalmazó elrendezést. Azt állítjuk, hogy n gyerek (2n-2)(2n-4)...42-féleképpen alkothat ,,kört''.
Állításunk bizonyításához tekintsük az egyik gyereket, pl. Pistit kiindulásnak. Ő a jobbkezével (2n-2) kezet foghat meg (mivel a feltételből következik, hogy senki sem fogja meg a saját kezét). Amelyik gyereknek megfogta valamelyik kezét, az a másik kezével már csak (2n-4) kezet foghat meg, (Pisti balkezét megfogva bezárná a kört). Így haladva az utolsó előtti gyerek még választhat valakinek a két keze közül, aki viszont a másik kezével megfogja Pisti balkezét. Ez (2n-2)(2n-4)...2 lehetőség, amit röviden (2n-2)!!-sal jelölünk, és 2n-2 szemifaktoriálisnak mondunk.
n=10 esetén ez 18!!. Ha a tíz gyerek nem alkot egy ,,kört'', akkor kisebb ,,körökbe'' rendeződnek (amelyek egymáshoz viszonyított helyzete minket nem érdekel). A körök mérete 2-től 8-ig változhat. Adott méretekhez tartozó elrendezések számát úgy kapjuk meg, hogy a gyerekeket az adott méretű csoportokba osztjuk, majd az egyes csoportokon belül egymástól függetlenül elkészítjük a lehetséges köröket.
Ha például két darab 3-as és egy darab 4-es kör jön létre, akkor először

(103)(73)(44)=(103)(73)-féleképpen
beosztjuk a gyerekeket, majd az egyes csoportokon belül (6-2)!!, (6-2)!!, illetve (8-2)!!-féleképpen elkészítjük a köröket. A beosztás során azonban megkülönböztetjük a két 3-as csoportot ‐ és általában az azonos méretűeket ‐ így itt minden lehetőséget 2-szer számolunk. Hasonlóan, a (2,2,2,4)-es csoportbeosztásokat például 3!=6-szor, a (2,2,3,3)-asokat pedig 2!2!-szor számoljuk. Mindezeket figyelembe véve az alábbi lehetőségek adódnak. A lista elején az adott felosztásban szereplő csoportok méretét soroltuk fel, ez a 10 összes lehetséges előállítása 2 és 8 közé eső számok összegeként.
10;(20-2)!!=185794560
 
2, 8;(102)(4-2)!!(16-2)!!=58060800
 
3, 7;(103)(6-2)!!(14-2)!!=44236800
 
5, 5;(105)(10-2)!!(10-2)!!/2=18579456,
 mert minden esetet kétszer számoltunk.
 
2, 2, 6;(106)(42)(4-2)!!(4-2)!!(12-2)!!/2=9676800
 
2, 3, 5;(105)(53)(4-2)!!(6-2)!!(10-2)!!=15482880
 
2, 4, 4;(102)(84)(4-2)!!(8-2)!!(8-2)!!/2=7257600
 
3, 3, 4;(104)(63)(6-2)!!(6-2)!!(8-2)!!/2=6451200
 
2, 2, 2, 4;(104)(62)(42)(4-2)!!(4-2)!!(4-2)!!(8-2)!!/3!=1209600
 
2, 2, 3, 3;(103)(73)(42)(4-2)!!(4-2)!!(6-2)!!(6-2)!!/(22)=1612800
 
2, 2, 2, 2, 2;(102)(82)(62)(42)((4-2)!!)5/5!=30240.
 

Ezek összege adja az összes lehetséges esetek számát, ami 387099936. A keresett hányados 1857945603870999360,48, tehát az eseteknek valamivel kevesebb, mint a felében alkot a tíz gyerek egyetlen ,,kört''.
 
Megjegyzés. Ha N gyereket akarunk elrendezni m1 darab c1, m2 darab c2, ..., mk darab ck méretű körbe (m1c1+m2c2+...+mkck=N), akkor ez
N!c!m1c2!m2...ck!mk1m1!m2!...mk!(c1!!)m1(c2!!)m2...(ck!!)mk
módon lehetséges.