Feladat: 446. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Biczó G. ,  Csáki E. ,  Deseő Zoltán ,  Durst E. ,  Dömölki Bálint ,  Kántor S. ,  Marik Miklós ,  Németh László ,  Rockenbauer Magda ,  Rozsondai B. ,  Schmidt E. ,  Szabó J. ,  Tahy Péter 
Füzet: 1952/december, 146 - 151. oldal  PDF  |  MathML 
Témakör(ök): Sakk, Kombinatorikai leszámolási problémák, Permutációk, Kombinációk, Sakktáblával kapcsolatos feladatok, Feladat
Hivatkozás(ok):Feladatok: 1952/április: 446. matematika feladat

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.

a) I. megoldás: 14 lépés esetén a bástya mindig csak a szomszédos mezőre léphet ‐ jobbra, vízszintes irányban, vagy előre függőleges irányban, mert a1-től h8-ig összesen 7‐7 egységlépést kell tennie mindkét irányban. Ha a vízszintes lépést a-val és a függőleges lépést b-vel jelképezzük; akkor egy tetszőlegesen kiragadott utat például így jelezhetünk: abbabaabbbaaba. Tehát minden útnak az aaaaaaabbbbbbb elemeknek egy permutációja felel meg és megfordítva: az említett permutációk mindegyikének egy út.
Ezek szerint az összes lehetséges utak száma (14 lépésben):

P147,7=14!7!7!=3432

Marik Miklós (Bp. I., Fürst S. g. II. o. t.)
 

II. megoldás: Minden mezőbe írjuk be az összes arra vezető utak számát elölről kezdve folytatólagosan. Ez utóbbi számot nyilván úgy kapjuk meg, ha összeadjuk abba a két mezőbe írt számot, amely két mezőről az illető mezőre léphettünk. (1. ábra)
 
 
1. ábra
 

Kiindulás: b1- és a2-be 1-et írunk s. i. t. a fenti szabály szerint. Ennek alapján a beírt számok olyan Pascal-féle háromszöget alkotnak, amelynek az a1 mező a csúcsa és melyben az a2-b1, a3-c1, a4-d1, a5-e1 stb. átlók a sorai. A h8 mezőbe tehát a 14. sor 8-ik tagja kerül:
(147)=3432
(L. lapunk III. évf. 325. sz. feladatát a 230. oldalon).
 

Németh László (Gyula, Erkel F. g. IV. o. t.)
 

III. megoldás: Az a8-h1 átló egyes mezeire a bástya a1-ből kiindulva feltételünknek megfelelően (70), (71), (72), (73) ...(76), (77)-féleképpen juthat el (L. előbbi megoldást és 1. ábrát.) Minden egyes mezőről a bástya nyilván ugyanannyiféleképpen mehet el h8-ra, ahányféleképpen eljutott az a8-h1 átló illető mezejére. Tehát az összes lehetséges utak száma
(70)2+(71)2+(72)2+...+(76)2+(77)2==2(12+72+212+352)=21716=3432.

Ennek a megoldásnak az az előnye, hogy egyszersmind megadja az a8-h1 átló minden egyes mezejére nézve külön-külön az illető mezőn átvonuló utak számát. Pl. f3-on (75)2=(72)2=212=441 út vonul át.
 

Tahy Péter (Bp. II., Rákóczi g. II. o. t.)
 

IV. megoldás: Állapítsuk meg egy tetszőleges n lépésszámra érvényes képletet, ahol n ‐ az értelmezésből kifolyólag ‐ természetes szám, melyre nézve 2n14.
Először is nyilvánvaló, hogy elég azokat az utakat megszámlálni, amelyekben az első lépés függőleges, mert ezen utaknak az a1-h8 átlóra vonatkozó tükörképei szolgáltatják a vízszintes kezdőlépésű utakat és fordítva. Tehát az összes utak száma: az előbbi kikötés mellett megszámlált utak kétszerese.
Mivel az utolsó lépés mindig h8-ra történik, ezért pl. valamely 12 lépéses út jelölésére elég azt a 11 mezőt megadni, amely mezőkön egy-egy lépés végződik. Valamely tetszőleges 12 lépéses utat pl. a következő 11 lépésvégponttal jelölhetünk a sakktábla mezeinek szokásos jelölését használva: a2-a3-c3-c4-d4-d6-e6-e7-f7-g7-h7. (2. ábra.)
 
 
2. ábra
 


A lépésvégpontok lehetnek olyan pontok, amelyekben irányváltozás történik és olyanok amelyekben nem történik irányváltozás. Ez előbbieket nevezzük töréspontoknak. Ezeknek számát k-val jelölve, n lépés esetén 1kn-1. Az utóbbiakat nevezzük megállók-nak. Ezeknek számát nyilvánvalóan megkapjuk, ha az n-1 lépés-végpontból a töréspontok számát levonjuk: n-1-k. (Ha k=n-1, akkor nincs megálló). A fenti példában 8 töréspontot találunk: a3, c3, c4, d4, d6, e6, e7, h7 és 11-8=3 megállót: a2, f7 és g7. (Az ábrában fekvő kereszttel jelölve).
A töréspontok teljesen meghatározzák az útvonalat (nem az utat, mert az út ismeretéhez még a megállók ismerete is szükséges), sőt elég pl. a vízszintes lépések végpontjainál lévő 82=4 töréspontot megadni (az ábrában nullkörrel jelölve), hogy az útvonal meg legyen határozva. Ezek szerint a fenti 12 lépéses út (függőleges indulást feltételezve) megadható a következő szimbólumokkal
c3,d4,e6,h7;a2,f7,g7.

Mivel a töréspontok száma jelen példában páros, azért az utolsó, vízszintes lépés végpontjában lévő töréspont, szükségképpen mindig a h oszlopba kerül és így >>h7<< helyett elég 7-et írni.
Tehát a
c3,d4,e6,h7;a2,f7,g7
szimbólumok teljesen megadják a fenti 12 lépéses utat, mégpedig a pontosvessző előtt álló szimbólumok meghatározzák az útvonalat, a pontosvessző után álló jelek pedig a megállókat adják meg.
Az útvonalat részben megadó c, d, e szimbólumok nem egyebek, mint a b, c, d, e, f, g elemeknek egy harmad osztályú kombinációja, az útvonalat másik részben megadó 3, 4, 6, 7 elemek pedig nem egyebek, mint a 2, 3, 4, 5, 6, 7 elemeknek egy negyed osztályú kombinációja.
Minden útvonal ‐ a kezdőpontot és végpontot nem számítva ‐ kivétel nélkül 13 mezőn halad át, tehát ha 13-ból levonjuk a töréspontok számát (k; jelen példánkban k=8), akkor a fennmaradó 13-k, jelen esetben 13-8=5 mezőn helyezkedhetik el az (n-1-k) számú, jelen esetben 11-8=3 megálló. Tehát a megállókat megadó 3 mező: a2, f7, g7 nem egyéb, mint az a2, b3, d5, f7, g7 öt mezőnek egy harmadosztályú kombinációja.
Mivel az itt szereplő 3 fajta kombinációs csoport mindegyikének bármely kombinációja kapcsolható egy másik kombinációs csoport bármely kombinációjával, azért az összes lehetséges utak számát megkapjuk, ha a 3 fajta kombinációknak számát összeszorozzuk.
Ezek szerint tehát a 12 lépéses és 8 törésponttal bíró utak száma
U12,8=2(63)(64)(53)=2(68-22)(682)(13-811-8)

Általában, ha a lépés szám n és a töréspontok száma k páros (2kn-1), akkor
Un,k=2(6k-22)(6k2)(13-kn-k-1).

Ha a töréspontok száma páratlan (1kn-1), akkor az utolsó töréspont (továbbra is függőleges kezdőlépést feltételezve) szükségképpen mindig egy függőleges lépés végpontja a 8. sorban. A függőleges lépések végpontjaiban lévő töréspontok száma tehát k+12 a vízszintes lépések végén lévő töréspontok száma pedig k-12. Ez utóbbiakat megadó szimbólumok egyrészt a
b,c,d,e,f,g
elemeknek, másrészt a
2,3,4,5,6,7
elemeknek egy k-12-ed osztálya kombinációja. Vagyis páratlan k esetén
Un,k=2(6k-12)2(13-kn-k-1).

A nyert két képlet egyesíthető a [x] jelölés bevezetésével (olvasd: x egész része<< v.entier [antjé] x), amely az x-ben foglalt legnagyobb egész számot jelenti.
Ugyanis, ha k páros, akkor
k-22=[k-12]ésk2=[k2],
ha pedig k páratlan, akkor
k-12=[k-12]=[k2],
és így
Un,k=2(6[k-12])(6[k2])(13-kn-k-1),
ahol n=2, 3, ..., 14 és k=1, 2, ..., n-1.
Az összes n lépéses utak számát, Un-et megkapjuk, ha rendre kiszámítjuk az utak számát k=1, 2, 3, ..., n-1 töréspont esetén és az így nyert eredményeket összeadjuk. Tehát
Un=2k=1n-1(6[k-12])(6[k2])(13-kn-k-1).
Képletünket jelen esetre alkalmazva, amidőn n=14
U14=2k=113(6[k-12])(6[k2])(13-k13-k),
vagyis
12U14=(60)2+(60)(61)+(61)2+(61)(62)+(62)2+(62)(63)+(63)2+(63)(64)++(64)2+(64)(65)+(65)2+(65)(66)+(66)2=2(1+6+36+90+225+300)+400=1716,


és így
U14=21716=3432.

Dömölki Bálint (Bp. IX., Apácai Csere János g. III. o. t.)
 

b) I. megoldás: Ha 12 lépésben akarunk h8-ra jutni, akkor vagy kétszer kell 2 egységnyit lépni, vagy egyszer 3 egységnyit. Ha az utóbbi lépéseket a2, b2 illetőleg a3, b3-mal jelöljük, akkor a következő elemek permutációjáról van szó:
  a  a  a  a2   a2   bbbbbbb  a  a  a  a  a3   bbbbbbb  a  a  a  a  a  a2   bbbbbb2  a  a  a  a  a  a  a  bbbbb3  a  a  a  a  a  a  a  bbbb2b2
Tehát
U12=2P122,3,7+P124,7+P125,5=212!2!3!7!+212!4!7!+12!5!5!=57024.

Deseő Zoltán (Bp. X., I. László g. II. o. t.)
 

II. megoldás: Alkalmazzuk az a) IV. megoldásánál nyert képletet:
12U11=k=111(6[k-12])(6[k2])(13-k11-k)==(1210)+6(119)+36(108)+90(97)+225(86)+300(75)+400(64)+300(53)++225(42)+90(31)+36(20)=66+330+1620+3240+6300+6300+6000++3000+1350+270+36=28512,


amiből
U12=57024.
 

c) I. megoldás:
Egy irányban 2 lépést a másik irányban 3 lépést megtéve az
aa6MMMbbb5a2a5bb2b4a3a4bb3b3a2a4b2b2b3
esetek lehetségesek.
Az első csoport minden sorát a második csoport minden sorával összekapcsolva és az így nyert 5 elemet esetről-esetre permutálva 3P5+9P52 számú utat kapunk, amely számot ‐ a és b felcserélhetősége miatt ‐ még 2-vel meg kell szorozni. Tehát ez esetben az utak száma 6P5+18P52.
Egy irányban 1 lépést a másik irányban 4 lépést megtéve az
a7MMMbnbbb4a7bbb2b3a7bb2b2b2
esetek lehetségesek.
Az utak száma ez esetben 2(P52+2P53)=2P52+4P53.
Tehát az összes utak száma
U5=6P5+20P52+4P53=651+205!2!+45!3!==720+1200+80=2000.



II. megoldás: A a) IV. megoldásnál nyert képletet alkalmazva:
12U5=k=14(6[k-12])(6[k2])(13-k4-k)=(123)+6(112)+36(101)+90(90)==220+330+360+90=1000,


és így
U5=21000=2000.