Valaki segítsene a matek hf-ben? (a feladat lent)

Kivételesen segítek benne, mert nem triviális a megoldás, pedig pofonegyszerű.

Először is tisztázzuk le, hogy a lehetséges szabályos lépéseket akarjuk megszámolni, nem pedig a betűk valamilyen sorrendiségét. A betűk csak azért vannak beírva ebbe a 7*6-os négyzetrácsba, hogy megmutassák nekünk a szabályt (hogyan léphetünk). Nem tudom érthető-e így vagy próbáljak rávilágítani valahogy máshogyan a feladat lényegére, de ha ezt nem érted, akkor nincs értelme továbbhaladni.

--

Ezek után: Az első megállapítás, amit meg kéne ejtenünk az az, hogy ez egy ismétléses permutáció lesz, mivel az összes elemet fel fogjuk használni (12-t léphetünk, mivel ennyiből áll a szó és 12-t is fogunk lépni!) és vannak benne azonos elemek is (jobbra és lefele lépések: nem csak egyszer, hanem többször is lépünk majd jobbra/lefele, ezek azonos elemek lesznek).

A képlet tehát amit használni fogunk: P = n!/(k1!*k2!), ahol "n" az összes elem száma; "k1", "k2" pedig a jobbra, illetve lefele lépések száma.

1. Mennyi lesz az "n" (összes elem)?

Mivel 12 betűből áll a szó, ezért 12-őt kell majd lépnünk, hogy ki tudjuk rakni, tehát az n=12 lesz.

2. Mennyi lesz a k1 és a k2? (k1: jobbra lépések; k2: lefele lépések)?

Ennek a megállapításához tanulmányoznunk kéne a lehetséges utakat és valami közöset kellene találnunk bennük, hogy működőképes legyen a képlet:

Mondjuk elsőként vizsgáljuk meg a triviális utat: Menjünk el teljesen jobbra, majd menjünk el teljesen lefelé és a lépéseket jelöljük be jobbra, illetve lefelé mutató nyilakkal. Hány jobbra nyilat kellett berajzolnunk? Hány lefele nyilat kellett berajzolnunk?

Ezután vizsgáljunk meg egy másik lehetséges útvonalat, akármilyent (én mondjuk átlóban kezdenék el menni, talán még az a legegyszerűbb): Hány jobbra nyilat és hány lefele nyilat kellett berajzolnunk?

Mi volt a közös a fenti kettőben? Na ugye, hogy ugye! Minden esetben 6 jobbra és 5 lefele nyilat kellett berajzolnunk és elárulom, hogy akármilyen útvonalat próbálsz, mindig ez fog kijönni.

Tehát k1=6, k2=5.

--

Behelyettesítve a képletbe:

P = 12!/(6!*5!)

Gondolom a számológép használata már menni fog, úgyhogy a végeredményt már nem számolom ki. :)

Egyébként a k1 és k2 között azért lesz szorzás, mert "ÉS" kapcsolat van közöttük: k1-et kell jobbra lépnünk ÉS k2-őt kell lefele lépnünk, hogy ki tudjuk rakni a szót, de ez csak extra info, ha esetleg tanultál eseményalgebrát és felmerülne kérdésként. Ha nem tanultál ilyet, akkor bőven elég tudni a képletet...

Ha 15:56-os válaszban vázolt módszerrel csináljuk, akkor arra lehetünk figyelmesek az első néhány összeg beírása után, hogy éppen egy Pascal-háromszög rajzolódik ki, csak a sorai átlósak a T betűkkel párhuzamosan. Valahogy így

1 1 1 1 1 1 1

1 2 3 4 5 6 7

1 3 610 … …

1 4 … …

1 5 …

1 6 … (Ha gondolod, akkor a leírom a teljes táblázatot, csak egyelőre nem akarom lelőni a végeredményt.)

Nem nehéz végigírni se, és akkor csak összeadásokkal kijön a helyes végeredmény, de talán tanultátok, hogy a Pascal-háromszög n-edik sorának k-adik eleme éppen (n alatt a k), csak arra kell figyelni, hogy az első B betű az n = 0-hoz tartozik, ahogy az ábra bal és jobb oldali szélei a k = 0-hoz illetve k = n-hez tartoznak. Így a záró E betű az n = 11-es átlón lesz, a k pedig 5 vagy 6 (annak függvényében, hogy a jobb vagy a felső szélet választottuk k = 0, de ez mindegy is, mert 5 + 6 = 11, ezért (11 alatt az 5) = (11 alatt a 6)).

Az (n alatt a k)-t számológépen szerencsés esetben az nCr vagy C gombbal ki tudod számolni, de ha beírod ide, hogy 11C5, akkor is megkapod a jó eredményt: [link]

Úgy is lehet gondolkozni, hogy összesen ugye 11-et kell lépni, ebből 5-öt lefelé. Hányféleképpen választhatjuk ki a 11-ből annak az 5-nek a sorszámát, ami lefelé történik? Ez pont ugyanolyan, mint a lottó: az elsőt választhatjuk 11-féleképpen, a másodikat ettől függetlenül 10-féleképpen, … az ötödiket 7-féleképpen, ami összesen

11*10*9*8*7

lehetőség, de ezt el kell osztani a sorrendek számával, mert hogy előbb a 8. aztán a 2. majd 7. lépést választottuk ki, hogy akkor lefelé lépünk, az pont ugyanolyan, mintha előbb a 7. majd a 2. aztán a 8. lépést választottuk volna, de ez mindegy, mert így is, úgy is előbb a 2. majd a 7. és 8. lépésben fogunk lefelé lépni sorban. Tehát ezt el kell még osztani az 5 sorszám összes lehetséges sorrendjével, ami

5*4*3*2*1

lesz. Így a végeredmény

11*10*9*8*7/(5*4*3*2*1)

lesz, amit még egy sima zsebszámológéppel is ki lehet számolni (főleg, ha előtte egyszerűsítjük a törtet 5-tel, 3-mal és 8-cal).

A 17:34-es gondolatmenete nagyon jó, ha tudjuk a végeredményt („ismétléses permutáció”, de mint látod a sima 'kombináció' is remekül indokolható), és a megoldás menetét visszafelé akarjuk felépíteni. Különben fordítva: próbáljuk meg lejegyezni egy utunkat a bal felsőből a jobb alsó sarokba. Ugye csak jobbra és lefelé léphetünk, tehát a J és L betűket fogjuk haszálni. Ezekből kell összerakni a 11 hosszú utat úgy, hogy jobbra 6-ot léphetünk, tehát 6 darab J betűnk van, lefelé pedig 5-öt, tehát 5 darab L betűnk van. 11 darab különböző betűt pedig 11! sorrendben tudnánk leírni, de most mivel a 6 darab J egyforma, ezért például azt az esetet, hogy a J betűk az első 6 helyen állnak 6!-szor számoltuk, ahogy bármelyik másikat is, pedig ezek a J betűk egyformasága miatt nem is különböznek. Így a 11!-t el kell osztani 6!-sal, de hasonló okokból el kell osztani 5!-sal is, mert az 5 darab L betű is egyforma. Így a helyes végeredmény

11!/(6!*5!).

Szerintem az összeadogatós módszer simán lehetett már 4.-ben vagy 5.-ben is.

Kapásból 5.-es szakköri feladatok között találtam hasonlót: [link] (17.2)

Itt 5.-eseknek van, de több végponttal: [link]

Még a faktoriális is előfordul már 7.-ben: [link]