Kunkun reitit
Kunkun reitit
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 ?
Sama juttu, mutta vaihtoehtona on myös siirto viistoon ylös-oikealle ?
Re: Kunkun reitit
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.
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.
Re: Kunkun reitit
Valitettavasti laskemasi tulos on väärä. Oikea vastaus on huomattavasti suurempi.
Re: Kunkun reitit
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.
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.
Re: Kunkun reitit
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
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
Re: Kunkun reitit
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

-
- Viestit: 233
- Liittynyt: 06 Tammi 2014 18:49
- Paikkakunta: Espoo
- Seura: MatSK
Re: Kunkun reitit
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
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
Re: Kunkun reitit
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.
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.
Re: Kunkun reitit
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
http://oeis.org/search?q=1%2C3%2C13%2C6 ... &go=Search
-
- Viestit: 343
- Liittynyt: 13 Heinä 2010 14:55
- Paikkakunta: Helsinki
Re: Kunkun reitit
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.
Paikallaolijat
Käyttäjiä lukemassa tätä aluetta: Ei rekisteröityneitä käyttäjiä ja 18 vierailijaa