Kunkun reitit

okkivas
Viestit: 65
Liittynyt: 08 Marras 2016 13:58
Paikkakunta: Salo

Kunkun reitit

Lukematon viesti Kirjoittaja okkivas » 16 Marras 2016 10:42

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

Re: Kunkun reitit

Lukematon viesti Kirjoittaja VJJJ » 16 Marras 2016 12:28

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
Viestit: 65
Liittynyt: 08 Marras 2016 13:58
Paikkakunta: Salo

Re: Kunkun reitit

Lukematon viesti Kirjoittaja okkivas » 16 Marras 2016 13:00

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

VJJJ

Re: Kunkun reitit

Lukematon viesti Kirjoittaja VJJJ » 16 Marras 2016 13:21

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
Viestit: 65
Liittynyt: 08 Marras 2016 13:58
Paikkakunta: Salo

Re: Kunkun reitit

Lukematon viesti Kirjoittaja okkivas » 16 Marras 2016 14:29

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
Viestit: 53
Liittynyt: 26 Elo 2012 14:36
Paikkakunta: Turku

Re: Kunkun reitit

Lukematon viesti Kirjoittaja V!RUS » 16 Marras 2016 19:36

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
Viestit: 169
Liittynyt: 06 Tammi 2014 18:49
Paikkakunta: Espoo
Seura: MatSK

Re: Kunkun reitit

Lukematon viesti Kirjoittaja Petri Pitkänen » 17 Marras 2016 08:39

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
Viestit: 65
Liittynyt: 08 Marras 2016 13:58
Paikkakunta: Salo

Re: Kunkun reitit

Lukematon viesti Kirjoittaja okkivas » 17 Marras 2016 14:43

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

Re: Kunkun reitit

Lukematon viesti Kirjoittaja VJJJ » 17 Marras 2016 18:43

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
Viestit: 298
Liittynyt: 13 Heinä 2010 14:55
Paikkakunta: Helsinki

Re: Kunkun reitit

Lukematon viesti Kirjoittaja Joose Norri » 18 Marras 2016 02:17

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.

Vastaa Viestiin

Paikallaolijat

Käyttäjiä lukemassa tätä aluetta: Ei rekisteröityneitä käyttäjiä ja 1 vierailija