Kunkun reitit

[okkivas]

Kuningas lähtee ruudusta a1 ja siirtyen ylös tai oikealle etenee ruutuun h8. Montako reittivaihtoehtoa sillä on ?

Sama juttu, mutta vaihtoehtona on myös siirto viistoon ylös-oikealle ?

[VJJJ]

Tarkastellaan ensin tilannetta, jossa kuningas liikkuu oikealle ja ylös. Tällöin siirryttäessä ruudusta a1 ruutuun h8 täytyy tehdä yhteensä 14 siirtoa, joista 7 on oikealle ja 7 ylös. Erilaisia reittejä on siis yhtä paljon kuin joukossa {1,2,...,14} on seitsemän alkion osajoukkoja. Tämä on edelleen sama kuin binomikerroin 14 yli 7:n eli 3432.

Tapaus, jossa kuningas voi liikkua oikealle ja ylös sekä viistoon ylä-oikealle, on jonkin verran monimutkaisempi tilanne. Itse en nopeasti keksinyt kombinatorista tapaa reittien lukumäärän laskemiseen. Tein kuitenkin pienen tietokoneohjelman, jonka avulla sain erilaisten reittien lukumääräksi 4356. Tulos vaikuttaisi ainakin uskottavalta sen suhteen, että mahdollisuuksia on enemmän kuin tuossa ensimmäisessä tapauksessa. Virheet ohjelmoinnissa ovat tietysti aina mahdollisia.

[okkivas]

Valitettavasti laskemasi tulos on väärä. Oikea vastaus on huomattavasti suurempi.

[VJJJ]

Olisin melko varma, että tuo ensimmäinen tulos (eli 3432) on oikein. Tämä on melko tavanomainen kombinatoriikan harjoitustehtävä.

Toisessa vastauksessa oli ohjelmaani tullut pieni leikkaa/liimaa-virhe. Tarkistuksen jälkeen sain tulokseksi 48639 erilaista reittiä. Mikäli tämä on oikein, niin olen hieman yllättynyt, että niitä on noinkin paljon enemmän verrattuna tuohon yksinkertaisempaan tilanteeseen. Intuitioni pettää näiltä osin.

[okkivas]

Oikein ja oikein.
Ensimmäisen tehtävän ratkaisu löytyy muuten Pascalin kolmiosta. Jos laudan koko olisi 1x1, 2x2, 3x3.......8x8, niin Pascalin kolmiosta löytyy luvut 1, 2, 6, 20, ..... 3432

[V!RUS]

Itse asiaan liittymätön kommentti: Otsikko toi mieleeni englantilaisen suurmestarin Nigel Shortin pelin, jossa hänen kuninkaansa lähti kävelylle voitokkain seurauksin http://www.chessgames.com/perl/chessgame?gid=1124533

[Petri Pitkänen]

Kombinatorisesti sen voi laskea jakamalla sen osiin reitin pituuden mukaan

14 on helppo ja se on esitetty jo, samten 7 koska reittejä on ilmeisesti 1. loppuihin sitten vaaditaan aavistus päättelyä

Vaikkapa 10 askeleen "perustapaus" on se, että otetaan neljä viistoaskelta ja sitten kolme vaakaan ja kolme ylös. Nyt nämä kolme vaakaan ja kolme ylös voidaan järjestää 6 yli 3 eri järjestykseen. ja tämä 6 ei-viistoaskeleen joukko voidaan poimia 10 askeleen joukosta 10 yli 6 tavalla.Josta saamme että kymmenellä askeleella tulee 4200 eri reittiä

7 1
8 56
9 756
10 4200
11 11550
12 16632
13 12012
14 3432

48639
Jos nyt oikein päättelin

[okkivas]

Minäkin laitan vielä lusikkani soppaan. Kun en hallitse noita kombinatioita, niin laskin vaihtoehdot seuraavasti:
Ruutuihin g8 ja h7 merkitään 1 koska niistä on vain yksi reitti perille. Ruutuun g7 merkitään 3 koska siitä on kolme vaihtoehtoa. Ruutuihin f8 ja h6 tulee ykköset. Ruutuun f7 tulee ruutujen f8, g7, g8 summa, joka on 5. Ruutuun g6 tulee myö 5. ruutuun f6 Ruutujen f7, g6, g7 summa, joka on 13. Elikkä 8-riville ja h-linjalle ruutuihin ykköset ja muihin ruutuihin ylä- ja oikealla- ja viistoon ylä/oikealla olevien lukujen summat.

[VJJJ]

Kombinatorisesti reittien lukumäärän pystyy todella laskemaan petrip:n esittämällä tavalla; ensin kiinnitetään reitissä käytettävien viisto-siirtojen lukumäärä ja jokaiselle näille saadaan erikseen lukumäärä. Nämä sitten summaamalla saadaan lopullinen vastaus. Tietokonehaussani käytin juuri okkivas:n kuvailemaa tekniikkaa. "The on-line encyclopedia of integer sequences" kertoo jotakin lukumääristä yleisesti, kun laudan kooksi ajatellaan nxn, missä n on jokin positiivinen kokonaisluku.

http://oeis.org/search?q=1%2C3%2C13%2C6 ... &go=Search

[Joose Norri]

Tämän ja lukemattomien vastaavien kysymysten perusteos on Bonsdorff, Fabel & Riihimaa: Schach und Zahl (1965, 2. laitos joskus 70-luvulla). Tavoitteena oli luonnollisesti löytää mahdollisimman elegantti matemaattinen lauseke. Tässä muodossa ei voine katsoa olevan mitään shakillista sisältöä, mutta tietysti nämä usein toimivat pohjana ns. shakkimatemaattisille tehtäville. Niissä useimmat laatijat pyrkivät siihen, että matemaattinen ja shakillinen puoli olisivat jotenkin tasapainossa. Jälkimmäinen voi esiintyä vaikkapa niin, että tarvitaan shakillinen oivallus siitä, mitkä mahdollisuudet on vähennettävä kokonaisuudesta tms.