Rauhalliset ratsut

Jos joku epäilee tulosten oikeellisuutta, niin alla on kaikki 244 vaihtoehtoa 3x3 laudalla. Laudan ruudut on numeroitu

0,1,2
3,4,5
6,7,8

Alla olevien nelinumeroisten lukujen kaksi ensimmäistä numeroa kertoo valkoisten ratsujen sijainnit ja kaksi jälkimmäistä mustien ratsujen sijainnit. Tarkistakaa muutama tapaus!

0123, 0124, 0134, 0214, 0216, 0218, 0246, 0248, 0268, 0314, 0316, 0346, 0412, 0413, 0416, 0418, 0423, 0426, 0428, 0436, 0438, 0468, 0512, 0513, 0514, 0518, 0523, 0524, 0528, 0534, 0538, 0548, 0623, 0624, 0628, 0634, 0638, 0648, 0713, 0714, 0716, 0718, 0734, 0736, 0738, 0746, 0748, 0768, 0824, 0826, 0846, 1204, 1205, 1245, 1304, 1305, 1307, 1345, 1347, 1357, 1402, 1403, 1405, 1407, 1423, 1425, 1427, 1435, 1437, 1457, 1523, 1524, 1527, 1534, 1537, 1547, 1602, 1603, 1604, 1607, 1623, 1624, 1627, 1634, 1637, 1647, 1734, 1735, 1745, 1802, 1804, 1805, 1807, 1824, 1825, 1827, 1845, 1847, 1857, 2301, 2304, 2305, 2306, 2314, 2315, 2316, 2345, 2346, 2356, 2401, 2405, 2406, 2408, 2415, 2416, 2418, 2456, 2458, 2468, 2514, 2518, 2548, 2604, 2608, 2648, 2714, 2715, 2716, 2718, 2745, 2746, 2748, 2756, 2758, 2768, 2804, 2805, 2806, 2845, 2846, 2856, 3401, 3405, 3406, 3407, 3415, 3416, 3417, 3456, 3457, 3467, 3514, 3517, 3547, 3604, 3607, 3647, 3714, 3715, 3716, 3745, 3746, 3756, 3804, 3805, 3806, 3807, 3845, 3846, 3847, 3856, 3857, 3867, 4512, 4513, 4517, 4518, 4523, 4527, 4528, 4537, 4538, 4578, 4602, 4603, 4607, 4608, 4623, 4627, 4628, 4637, 4638, 4678, 4713, 4715, 4716, 4718, 4735, 4736, 4738, 4756, 4758, 4768, 4802, 4805, 4806, 4807, 4825, 4826, 4827, 4856, 4857, 4867, 5623, 5624, 5627, 5628, 5634, 5637, 5638, 5647, 5648, 5678, 5713, 5714, 5718, 5734, 5738, 5748, 5824, 5827, 5847, 6734, 6738, 6748, 6802, 6804, 6807, 6824, 6827, 6847, 7845, 7846, 7856

Täysin oikein! Tai siis ainakin itse saan samat, joten luultavasti :D.

Vakioaikainen algoritmi on kuitenkin olemassa ja sen löytäminen aika mielenkiintoinen pähkinä.

Esimerkiksi:

n=100: 2490750884432120
n=1000: 249990524114158110222320
n=100000: 2499999990500240011474408001065372794320

Noiden lukujen muoto tietenkin kielii siitä, että siellä on jokin johtava termi. Johan se on nähtävissä siitäkin, että kun lauta kasvaa suureksi, tulee uhkauksien merkitys entistä mitättömämmäksi ja ratsut saavat sijaita melkein kuinka vaan laudalla. No, en nyt paljasta enempää, mutta innostuin vähän ja kirjoitin juttua vastaavasta neljän saman värisen ratsun tehtävästä:
https://membolicsythod.home.blog/2019/06/17/rauhalliset-ratsut/
Kannattaa kokeilla vastaavaa tehtävää ensin kolmelle ratsulle, joka sen alkuperäinen muoto ohjelmointiputkassa olikin, missä tähän tehtävään törmäsin: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=kunhev

Tuolla blogissa on muuten juttua myös muista täälläkin palstalla esiintyneistä tehtävistä kuten Vangin pasianssi ja mikäs se toinen oli .. ai niin se suorakaide-tehtävä, mutta en ole vielä julkaissut sitä artikkelia, kannattaa pysyä linjoilla jos kiinnostaa.. :D

Poistamalla valkoisten ratsujen reunojen yli menevät ja päällekkäiset varaukset saadaan 1000x1000 kahden ratsun keskimääräiseksi ruutujen varausluvuksi 17.9519861838. Pitää laskea vain valkoisten ratsujen n. 500 miljardia kombinaatiota! Kaavassa 18 korvautuu tuolla ja 19 muuttuu 18.9519861838:ksi. Tulokseksi saadaan

n = 1000: 249990524101190492356608

Alkaa olla kohta tarkempi kuin ihan tarkka luku!

Anonyymi kirjoitti:

Poistamalla valkoisten ratsujen reunojen yli menevät ja päällekkäiset varaukset saadaan 1000x1000 kahden ratsun keskimääräiseksi ruutujen varausluvuksi 17.9519861838. Pitää laskea vain valkoisten ratsujen n. 500 miljardia kombinaatiota! Kaavassa 18 korvautuu tuolla ja 19 muuttuu 18.9519861838:ksi. Tulokseksi saadaan

n = 1000: 249990524101190492356608

Alkaa olla kohta tarkempi kuin ihan tarkka luku!

Lue lisää

Olin nopeuttanut ohjelmaa virheellisesti ja ohjelma jätti huomioimatta kaukaisimmat yhteiset uhkaukset. Oikea ruutujen keskimääräinen varausluku onkin 17.9519603276 ja sillä saadaan tulokseksi:

n = 1000: 249990524114118310363136

Kolme oikeaa numero lisää. Tarkka luku näyttää olevan ihan oikea!

(n^2-1)*n/2 * (n^2-a)*(n^2-b)/2
=
1/4 * (n^8 - (1 b a)n^6 (a b ab)n^4 - (ab)n^2 )

Kun
a = 18.9519861838
b = 17.9519861838,
niin
1 b a = 37.9 = 38
Kyllä, kyllä oikealta näyttää! Pyöristämällä päästäänkin oikeaan kertoimeen :D

a b ab = 377.1 Tämä heittää jo vähän enemmän ja viidennen asteen termi puuttuu välistä. Ratkaisu on siis, paljastettakoon: polynomi!

Voisikohan viidellekin ratsulle vain laskea arvon tarpeeksi monessa pisteessä ja päätellä niistä mikä polynomi ratkaisun on oltava? Se siinä vaan vielä on, että siinä on aina jokin alaraja mistä lähtien polynomi alkaa antamaan arvon ja pitäisi tietää mikä se viiden tapauksessa on ja sitten vielä jotenkin laskea tarpeeksi monessa ja siis tarpeeksi isoissa pisteessä se arvo.
Periaatteessa sitä inkluusio-eksluusio ratkaisuakin voisi koittaa, mutta siinä olisi 5C2 = 10 ehtoa ja niistä tulee melko monia erilaisia leikkaustyyppejä. Miten esimerkiksi 5-ketjujen määrän voi graafilta laskea? Tai no, varmaan niitä voisi eri n:n arvoille laskea ja sitten arvata kaavan, jos siinä näkyy joku systemaattisuus.