Hogyan lehet megoldani az ilyen jellegű fejtörőket?

Az első megoldásával csak annyi a gond, hogy függ a korábbi lépésektől, hogy mikor jutunk el a szélére.

Első megoldás; ne az egészet nézzük, csak a részeket. Azt fogjuk vizsgálni, hogy egy adott mezőbe hányféleképpen lehet eljutni.

Úgy vesszük, hogy a kiinduló mezőbe 1-féleképpen lehet eljutni. Az első sor és az első oszlop mezőibe szintén 1-féleképpen (csak jobbra vagy csak felfelé lépünk), így ezekbe a mezőkbe 1-est írunk.

Most nézzük azt hogy a kiinduló mezőből hányféleképpen lehet eljutni a vele átlósan álló mezőbe. Nem nehéz leszámolni, hogy 2-féleképpen (jobbra-fel és fel-jobbra), viszont ezt úgy is kiszámolhattuk volna, hogy megnézzük, hogy a vele szomszédos mezőkből hányféleképpen lehetne odajutni; annyiféleképpen, ahányféleképpen azokba lehet jutni összesen; az egyik szomszédos mezőbe 1-féle út volt, a másikba is, összesen tehát 1+1=2-féle utat számolhatunk meg.

Általánosan tehát azt mondhatjuk, hogy egy adott mezőbe annyiféleképpen lehet eljutni, amennyi a tőle balra és alatta található mezőkbe írt számok összege.

7x7es táblázatod így fog kinézni (valószínűleg el fog csúszni, így érdemes soronként nézni, és úgy beírni a számokat:

1 7 84 210 462 924

1 6 56 126 252 462

1 5 15 35 70 126 210

1 4 10 20 35 56 84

1 3 6 10 15 21 28

1 2 3 4 5 6 7

1 1 1 1 1 1 1

Értelemszerűen a jobb felső sarokba kerülő szám mutatja meg, hogy hányféleképpen lehet eljutni a jobb felső sarokba, tehát 924-féleképpen lehet odajutni.

Ennek az eljárásnak az az előnye, hogy bármikor használható (még akkor is, hogyha "lyukas" a táblázat, vagyis vannak tiltott mezők, ahova nem léphetünk - azokba csak 0-t írunk, és minden más ugyanúgy megy, ahogy fent írtam), hátránya viszont -mint általában az indukciós módszereknek)-, hogy lépésről-lépésre lehet csak vele haladni, tehát mondjuk már egy 20x20-as táblázathoz nagyságrendileg 400 összeadást kell elvégezni, ami azért nem kevés.

Érdemes észrevenni, hogy a fenti táblázatban valójában egy Pascal-háromszög keletkezik (pontosabban egy része):

[link]

Második megoldás; ehhez már a kombinatorika eszközeit kell segítségül hívnunk; a teljesség igénye nélkül, hogyha n esetben tudunk jobbra lépni és m esetben felfelé, akkor

(n+m)!/(n!*m!)

-féleképpen lehet eljutni az egyik helyről a másikba, ahol a felkiáltójel a faktoriálist hivatott jelölni, ami azt jelenti, hogy az előtte álló pozitív számtól kezdve összeszorozzuk az egész számokat 1-ig, például 5!=5*4*3*2*1=120, 10!=10*9*8*7*6*5*4*3*2*1=3.628.800, stb, ha pedig az előtte álló szám 0, akkor definíció szerint az értéke 1, tehát 0!=1.

Esetünkben 6-szor tudunk balra és 6-szor felfelé lépni, tehát:

(6+6)!/(6!*6!) = (12*11*10*9*8*7*6*5*4*3*2*1)/(6*5*4*3*2*1*6*5*4*3*2*1) = 479001600/518400 = 924

Ha érdekel, hogy miért lehet így is számolni, külön kérésre leírom.

A számításnak az a nagy előnye, hogy nem kell egyesével kitölteni a táblázatot, bármelyik mezőbe való eljutási lehetőséget ki lehet vele számolni, HA nincs tiltott mező a táblázatban. Ha van tiltott mező, akkor már sokkal nehezebb vele számolni, akár már egyszerűbb manuálisan kitölteni a táblázatot.

Ha valaki járatosabb a témakörben, akkor azt is észreveheti, hogy a fenti képlet megadható

(n+m alatt az n) vagy (n+m alatt az m)

alakban, ami a kombinációszámításból fakad. Ennek pedig az a vonzata, hogy a Pascal-háromszög minden tagja felírható (n alatt a k) alakban, ahol n a tag sorszámát jelöli, k pedig a sorban elfoglalt helyét (ehhez viszont még azt is kell tudni, hogy a számozást nem 1-től hanem 0-tól kezdjük, tehát 0. sor, 1. sor, 2. sor, stb. illetve ugyanez a sorban elfoglalt hellyel is).

________

A másik alakú problémánál jöhet elő az, amit az első válaszoló felvázolt, ugyanis ott minden esetben tudunk vagy jobbra vagy felfelé lépni, amíg el nem érünk a végéhez. Ha n darab lépési lehetőség van, akkor 2^n-féleképpen lehet eljutni az utolsó mezők valamelyikébe, ahol ^n a kitevőt hivatott jelölni, vagyis

2^n = 2*2*2*2*...*2, ahol a szorzatban n darab 2-es van. Ha n értéke véletlenül 0 lenne, akkor 1 darab mező van az egész táblázatban, ahhoz pedig egyféleképpen lehet eljutni, és definíció szerint 2^0 értéke is 1, tehát nincs baj. Esetünkben 2^6=64-féle kiolvasási lehetőség létezik.

Ez a táblázat is ugyanúgy kitölthető, mint ahogyan az előbb felvázoltam. Abban az esetben az eredményt úgy kapjuk, hogy a végeken található számokat összeadjuk:

1

1 6

1 5 15

1 4 10 20

1 3 6 10 15

1 2 3 4 5 6

1 1 1 1 1 1 1

Tehát 1+6+15+20+15+6+1=64-féleképpen olvasható ki a szó.

Ennek a példának az a vonzata, hogy a Pascal-háromszög n-edik sorában található számok összege mindig 2^n.

"Itt több ezer lehetőség van, szóval összeszámolni egyesével lehetetlen. Tehát biztos kell lennie valami olyan módszernek, amivel az ilyen típusú feladványokat meg lehet oldani."

Nem lehetetlen összeszámolni egyesével, csak sokáig tart, és persze annak is nagy a valószínűsége, hogy valami kimarad, de nem lehetetlen. Ráadásul ebből sajnos korántsem következik az, hogy lennie kell egyszerűbb számítási módnak. Szerencsére ennek van, de általában nem mondható az, hogy minden problémának van egyszerűbb számítási módja.

Ha valami nem világos, vagy szeretnéd részletesebben tudni, akkor írj nyugodtan.