Egy könyvespolcon 36 könyv van. Hányféleképpen lehet kihúzni 11 nem szomszédos könyvet?

Ilyen valszám példánál az segít nagyon sokat, ha megtalálod a jó vizualizációt a problémához.

Itt nem lehet két egymás melletti könyvet kihúzni. Emiatt hozzunk olyan blokkot létre, amikor egy kihúzott könyv és annak a bal oldalán lévő nem kihúzott könyvet csoportosítjuk. Ekkor van 11 ilyen blokkunk, és 12 magányos könyvünk. Ha ezeket a blokkokat, és könyveket pakolod egymás mellé, akkor nem kerülhet egymás mellé kihúzott könyv, tehát a problémának mefelel, és egy kivételével minden lehetséges húzást lefed. Ennek a 23 résznek az elrendezési módja 23 alatt a 12 mivel a sorrend nem számít. Az az egy eset nincs benne, amikor a legbaloldalabbi könyvet is kihúzzuk, emiatt ezt még hozzá kell adni. Ekkor mivel egyet már kihúztunk, emiatt csak 10 másik kihúzottnak kell a blokkban lennie ekkor 10 kettős, és 12 magányos blokk van, aminek az elrendezése 22 alatt a 10.

Tehát az eredmény

(23) (22)

( ) + ( )

(12) (12)

Persze ha a kihúzás sorrendje is számít, akkor

23!+22!

A 2-es tanácsát egy kicsit átfogalmaznám; minden esetben érdemes valamilyen kódsorban gondolkodni. Olyan kódsor jó, ami kölcsönösen egyértelműen leírja az összes esetet, vagyis minden kódsor pontosan 1 esetet jelöl, és minden eset pontosan egy kódsorral írható le.

Először kezdjük azzal, hogy beiktatunk még egy könyvet a végére, és átfogalmazzuk úgy a feladatot, hogy az utolsó könyv nem választható (látni fogjuk, hogy ennek mi a jelentősége), ezzel az extra megkötéssel láthatóan nem változott az eredeti feladat. Így 37 könyvünk van összesen.

Haladjunk balról-jobbra a könyvek kiválasztásában. Ha nem választunk ki egy könyvet, akkor nincs semmi gond, ha viszont egy könyvet kiválasztunk, akkor a közvetlenül tőle jobbra lévő könyvet már nem választhatjuk ki. Ezt a következő módon jelölhetjük; ha nem választunk ki egy könyvet, akkor alá egy 1-est írunk, ha kiválasztunk egyet, akkor az alá és a tőle jobbra lévő alá (összevontan) egy 2-est írunk. Ez azért jó, mert így minden esethez tudunk pontosan egy kódsort rendelni. Kérdés, hogy fordítva működik-e; például ki tudjuk-e olvasni a

21121121221111212122111122

kódsorból, hogy mely könyvek lettek kiválasztva? És erre a válasz az, hogy igen; az 1., az 5., a 9., a 12., a 14., a 20., a 23, a 26., 28., 34., és a 36-dik. Ebből látható, hogy ezért volt érdekes +1 könyvet beiktatni, mert különben nem írhatnánk 2-est a végére (és ha 1-est írunk, az csak annyit jelent, hogy az utolsó könyv nem lett kiválasztva, ami pont jó).

Ha ezt sikerült felfedeznünk, akkor már csak az a kérdés, hogy a fenti számok hányféleképpen írhatóak egymás mellé, ezt pedig egy egyszerű ismétlés nélküli permutációval (vagy ismétlés nélküli kombinációval) meg tudjuk határozni: 26!/(11!*15!) (ismétlés nélküli kombinációval (26 alatt a 11) ).

Ezzel a megoldással csak annyi a baj, hogy nem ugyanazt adja eredményül, mint a 2-es megoldása, és nem találok egyikben sem hibát. Sajnos idő híján csak később tudok vele behatóbban foglalkozni.

#2

"Ekkor van 11 ilyen blokkunk, és 12 magányos könyvünk."

Becsúszott egy triviális számolási hiba: 36 könyv és 11 dupla = 14 magányos. Egyébként tényleg nagyon jó a megoldás. :-)

„Ekkor van 11 ilyen blokkunk, és 12 magányos könyvünk.”

Itt lesz a hiba, ugyanis a 11 (két könyves) blokk és a 12 magányos könyv összesen csak 34 könyv, viszont eredetileg 36 könyv van, tehát a magányos könyvek 14-en vannak.

#3

"Annyit még megjegyeznék, hogy az én megoldásom több esetet ad meg"

El kell különítenünk 3 megoldáscsoportot:

- amikor az utolsó valódi könyvet kiválasztják: akkor az utolsó számjegy kötelezően 2. Ha ezt levágjuk, akkor marad 11 db 2-es és 14db 1-es.

- amikor az utolsó valódi könyvet nem választják ki de az előtte levőt igen, akkor az utolsó két számjegy kötelezően 21.

- amikor az utolsó valódi könyvet nem választják ki és az előtte levőt sem, akkor az utolsó két számjegy kötelezően 11.

Ha az utóbbi két esetben az 1-est levágjuk, akkor marad 12 db 2-es és 14db 1-es.

(25 alatt 14)+(26 alatt 14)

Ha a 6-osban javasolt korrekciómat bevezetjük 2-es eredményébe, akkor a két eredmény ugyanaz lesz.

A Te megoldásod is tetszik, mert egyértelmű, hogy a könyveken balról jobbra haladva és a kiválasztásről egyesével döntve, a számsor 1 az 1-ben rögzíti a végeredményt.

„El kell különítenünk 3 megoldáscsoportot”

Vitatkoznék azzal, hogy „kell”. Szerintem egyértelmű, hogy az így kreált kódsor kölcsönösen egyértelmű az esetek számával. Azért lett bevezetve a +1 könyv, hogy ne kelljen a szélső könyvvel vacakolni.

Azt pedig azért írtam, hogy több eredményt ad a számolás, mert kicsit belekavarodtam #2 megoldásába, és csak később esett le, hogy elszámolta a könyveket, ezért nem jött ki ugyanaz az eredmény (annak ellenére, hogy a gondolatmenet gyakorlatilag ugyanaz a két számolásban, csak az én megoldásom (számomra legalábbis) jobban átlátható). De köszönöm az észrevételeket.

Még annyi megjegyzést tennék, hogy ha nem balról-jobbra haladunk, hanem a könyvek kihúzási sorrendjei között különbséget teszünk, akkor egyszerűen a kapott eredményt meg kell szoroznunk 11!-sal, mivel minden számolt esetben a 11 könyv ennyi módon húzható le a polcról.

"Azért lett bevezetve a +1 könyv, hogy ne kelljen a szélső könyvvel vacakolni."

Muszáj vacakolni vele, mert az nem ugyanolyan, mint a többi. Nem választható.

"#2 ... elszámolta a könyveket, ezért nem jött ki ugyanaz az eredmény..."

Ha figyelembe vesszük a javítást, hogy 14 magányos könyv van, akkor #2 eredménye: (26 alatt 14)+(25 alatt 14).

A Tied (az én javasolt korrekcióm nélkül): (26 alatt a 11). Nem ugyanannyi.

"az én megoldásom (számomra legalábbis) jobban átlátható)."

Egyetértek. Számomra is.