Page 45 - Tuzson - Hogyan oldjunk - mutatvany

23. Útvonalak száma, rekurzív számlálással

Napjainkban is gyakran találkozhatunk olyan feladatokkal, ahol azt kell megszámolnunk,
hogy adott pontból, vagy pontokból kiindulva, adott feltételek mellett hányféleképpen juthatunk
el egy másik pontba, vagy pontokba. Ezen feladattípusok egy másik változata az, amikor azt kell
megszámlálnunk, hogy adott feltételek mellett, hányszor olvasható ki egy szó, egy adott
betűelrendezésből. Ilyen feladványról már a 8.1. fejezetben, a fordított út módszerénél is beszél-
tünk, ahol a 64. oldal 7. példája, illetve a 72. oldal 20. a) és b) feladatai a következők voltak:
Hányféleképpen olvasható ki a MATEK szó, ha mindig a táblázat valamelyik M betűjé-
ből indulunk ki, és a betűket balra, jobbra vagy lefelé haladva olvashatjuk? Ugyanez a kérdés
a VAKÁCIÓ szó esetén, az a) esetben balra nem olvashatunk:
V A K Á C I Ó V
M A K Á C I Ó V A V
M A M K Á C I Ó V A K A V
M A T A M Á C I Ó V A K Á K A V
M A T E T A M C I Ó V A K Á C Á K A V
M A T E K E T A M I Ó V A K Á C I C Á K A V
Ó V A K Á C I Ó I C Á K A V
Az érdeklődő Olvasóban azonnal fölmerülhet a kérdés, hogy ezek a feladattípusok csak a
fordított út módszerével oldhatók meg? Nem, az ilyen feladatok direkt módszerrel is meg-
oldhatók, amit a következőkben mutatunk be. Ugyanakkor megjegyezzük, hogy ezek a felada-
tok a kombinatorika tárgykörébe tartoznak, de a továbbiakban éppen arra akarunk rávilágítani,
hogy az említett feladattípusok hogyan oldhatók meg az elemi és a gimnáziumi osztályokban
is. Természetesen ezután rámutatunk a feladatok a kombinatorikai hátterére is. Így minden bi-
zonnyal sokkal érdekesebbé és vonzóbbá tehetjük a kombinatorika tanítását, akár már kisebb
osztályosok esetén is.
A
1. feladat
A mellékelt ábrán egy úthálózat látható. Jancsi, az A
pontban levő lakásából indulva, a B pontban levő iskolába a
lehető legrövidebb úton akar eljutni. Hányféleképpen teheti
meg ezt?
Megoldás 1.a. ábra B
Reménytelen lenne az összes utat bejárni, hiszen mint látni fogjuk, ez nem is kevés.
Anélkül kellene megállapítanunk ezt, hogy ne kelljen egyenként megszámolni a lehetőségeket.
Először is vegyük észre, hogy az A → 1 → 1 → 1 → 1 → 1 → 1
A pontból a B pontba vezető legrövi- ↓ ↓ ↓ ↓ ↓ ↓ ↓
debb utak éppen azok, amelyek éppen 1 → 2 → 3 → 4 → 5 → 6 → 7
6 vízszintes és 4 függőleges rácssza-
↓ ↓ ↓ ↓ ↓ ↓ ↓
kaszból álló „törött vonalak”, amelyek- 1 → 3 → 6 → 10 → 15 → 21 → 28
nek kezdőpontja A, végpontja pedig B. ↓ ↓ ↓ ↓ ↓ ↓ ↓
A feladat kérdését úgy is átfogalmaz-
1 → 4 → 10 → 20 → 35 → 56 → 84
hatjuk, hogy hányféleképpen juthatunk
↓ ↓ ↓ ↓ ↓ ↓ ↓
az A pontból a B-be, ha csak jobbra 1 → 5 → 15 → 35 → 70 → 126 → 210
vagy lefele haladhatunk az úthálózaton. 1.b. ábra
A mellékelt 1.b. ábrán az egyes rács-
pontokra írt számok azt mutatják, hogy az illető rácspontra (a jobbra vagy lefelé feltétellel)
hány út visz. Az első sor, illetve első oszlop rácspontjaira 1-et kell írnunk. Minden másik

240