Sijoitetaan 8x8 ruudun shakkilaudan jokaiseen ruutuun jokin numeroista 0,...,9 siten, että toisiaan joltakin sivulta tai vinoittain koskettaviin ruutuihin tulee aina eri numerot.
Yksinkertainen esimerkki olisi vaikkapa seuraava:
01234567
23456789
45678901
67890123
89012345
01234567
23456789
45678901
Kysymys kuuluu seuraavasti:
Mikä on kaikkien mahdollisten ratkaisujen kokonaislukumäärä?
Yksinkertainen esimerkki olisi vaikkapa seuraava:
01234567
23456789
45678901
67890123
89012345
01234567
23456789
45678901
Kysymys kuuluu seuraavasti:
Mikä on kaikkien mahdollisten ratkaisujen kokonaislukumäärä?
Vastaukset 10
Vanhimmat
tarkan ratkaisun löytääkseen pitäisi kai olla joku Oxfordin tai Cambridgen matematiikkaguru?
... jopa minulle. Oletko varma, että tähän löytyy yksinkertaista ratkaisua? Tuo vinottaisuus tekee tästä vaikean.
... etsi tietoa haulla 'diagonal Latin Square'.
Huomaa, että jotkut lähteet määrittelevät tuon kuitenkin niin, että vain päädiagonaalit lasketaan. Yleensä rivit myös täytetään niiden pituutta vastaavan kokoisella merkistöllä.
Eivät kirjailijat varmaankaan piruuttaan rajoita yksinkertaisiin tapauksiin, vaan edes niistä tapauksista ei vielä tiedetä kaikkea!
Esim. ratkaistujen Sudoku-ruudukkojen kokonaismäärät (symmetrioiden kanssa tai ilman) löydettiin vasta vastikään käyttämällä logiikan ja raa'an tietokonetehon yhdistelyä.
... vinottaisuus-ehto poistettaisiin, ei ole mitään helppoa kaavaa tai kikkaa millä näitä voitaisiin yleisesti laskea. Kun mitat ylittävät 11 x 11, määriä ei edes tunneta, vaikka merkistökoko vastaisi rivikokoa.
Ainoat tunnetut metodit yhdistelevät logiikkaa ja raakaa laskentatehoa.
... tämä ei olekaan ihan sama kuin Latin square, sillä luvut saavat toistua samalla rivillä, kunhan eivät ole vierekkäin.
Siksi tämä on näköjään suhteellisen helppo laskea, ainakin ilman vinottaisuus-ehtoa.
yksinkertainen ratkaisu tai ainakin pari vihjettä ja oikea lopputulos. Sehän näyttäisi pikaisesti tarkasteltuna olevan noin 50-55 numeroinen kokonaisluku.
kommentit tähän tehtävään lienee syytä unohtaa. Tehtävän ratkaisulla ei liene mitään tekemistä latinalaisten neliöiden ongelman kanssa (kuten hän itsekin lopulta asiaa hiukan pohdittuaan toteaa). Ehkä nimimerkillä on tapana puhua nopeammin kuin ajattelee? Tämä ei sinänsä ole paha tapa, sillä se on kaiken dialogin alku ja perusedellytys (brainstormaus?, seinätaulumenetelmä?)
Sen sijaan ns. neljän värin probleema tuo hiukan lisävalaistusta asiaan. Neljän värin teoreemasta nimittäin seuraa, että shakkilaudan peittämiseen tehtävän kuvaamalla tavalla riittää neljä numeroa ('väriä').
Yksinkertainen esimerkki voisi olla
0101010101
2323232323
0101010101
2323232323
0101010101
2323232323
0101010101
2323232323
Kun 'värejä' (numeroita) on käytettävissä 10 kappaletta, ratkaisujen lukumäärä on huomattavasti minimimäärää suurempi.
Ehkä nimimerkin nkorppi kannattaisi tutustua kombinatoriikan ja verkkoteorian perusteisiin, joihin neljän värin teoreemakin nykyään kuuluu.
ei ehkä voi tähän tehtävään suoraan soveltaa. Se nimittäin edellyttää, että 'vierekkäisillä' alueilla on yhteistä rajaviivaa. Joku muunnelma ehkä toimisi.
Tässä tehtävässä on kuitenkin ilmeistä, että neljä väriä riittää tehtävän ratkaisemiseen. Tämä selviää esitetystä ratkaisuesimerkistä. Toisaalta tarkastelemalla mitä tahansa 2x2 ruudun aluetta huomataan, että vähintään neljä väriä ('numeroa') välttämättä tarvitaan.
Ala- ja ylärajat ratkaisujen lukumäärälle saadaan seuraavasti.
Lähdetään täyttämään shakkilautaa numeroilla 0,...,9 alkaen ylimmän rivin vasemmasta reunasta ja edeten rivi riviltä vasemmalta oikealle. Helposti todetaan, että ensimmäinen numero voidaan valita 10 eri tavalla ja kukin ensimmäisen rivin seuraavista luvuista aina 9 eri tavalla. Toisen rivin ensimmäinen luku voidaan valita 8 eri tavalla, toinen-seitsemäs luku 6 tai seitsemällä eri tavalla ja rivin viimeinen luku 7 eri tavalla. Sama koskee rivejä 3-8 ylhäältä lukien. Mahdollisten valintojen lukumäärille saadaan siis seuraavat arvot:
10,9,9,9,9,9,9,9
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
8,6-7,6-7,6-7,6-7,6-7,6-7,7
Ratkaisujen minimilukumääräksi saadaan siis
10*9^7*8^7*7^7*6^42 =39752667047161257462251187531655465275395489912586240 (n. 3.975266705*10^52)
ja maksimilukumääräksi
10*9^7*8^7*7^49=25771009777909292567313419046385877526291106993180508160 (n. 2.577100978*10^55)
Tarkka arvo on siis tässä haarukassa.
että vasemman yläkulman 2x2 ruutuun voidaan luvut ('värit') valita mielivaltaisella tavalla, esim. siten, että ne ovat
01
23
Tehtävän määrityksen perusteellahan näiden lukujen pitää olla eri suuria.
Numeroiden 0,...,9 välisen symmetrian vuoksi jokaista mahdollista valintaa vastaa täsmälleen yhtä monta erilaista ratkaisua.
Koska nämä luvut voidaan valita 10*9*8*7 = 5040 eri tavalla, voimme päätellä, että kaikkien mahdollisten ratkaisujen lukumäärä on jaollinen luvulla 5040 (eikö niin, dillet?)
Mitähän muuta erilaisten symmetrioiden perusteella erilaisten ratkaisujen kokonaislukumäärästä voitaisiin päätellä?