Yhdellä merkillä ruudukon vajaa täyttö osoittautui aivan liian helpoksi.
Palstan matemaatikoille hiukan haastetta täyttää koko ruudukko aivan täyteen kahdella eri merkillä (värillä). Minkään neliön kaikissa neljässä nurkassa ei saa olla samaa merkkiä.
Täytin 14x14 ruudukon täysin satunnaisesti. Helppo löytää useita erilaisia. Jos johonkin ruutuun ei pystytty lisäämään kumpaakan merkkiä, jokaisesta jumittavasta neliöstä poistettiin satunnaisesti yksi kolmesta nurkasta ja ruutuun laitettiin merkki, jota oli vähiten. Täytettyjen merkkien määrä pienenee aina jumitilanteissa useallakin merkillä, mutta aina pääsee jatkamaan uudesta (toivottavasti) erilaisesta (?) tilanteesta. Max yrityksen jälkeen luovutaan ja aloitetaan alusta.
0 1 0 1 1 1 0 0 0 1 1 0 1 0
0 1 1 1 0 0 1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0 1 1 1 1 0 1
0 0 0 1 1 1 1 0 0 1 0 1 0 0
0 1 0 0 1 0 1 0 1 0 0 1 1 0
1 0 0 1 0 0 1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1 0 0 0 1 0 1
1 0 1 0 0 0 1 0 0 1 1 1 1 1
1 1 0 0 1 1 1 1 0 0 1 0 0 1
0 1 1 0 0 1 0 1 0 1 0 0 1 0
0 0 1 0 1 0 0 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 0 0 0 1 1
0 0 0 1 0 1 0 1 0 0 1 1 1 0
1 1 0 1 1 0 0 0 0 1 1 0 1 0
196 98 98
Täytetystä 14x14 ruudukosta voi valita eri tavoin useita pienempiä täytettyjä ruudukoita. Valitkaa vaikka joku 4x4 tai 5x5 alue ja hakekaa siitä virhe. Jos ette löydä virhettä, yrittäkää uudestaan tai tehkää ohjelma joka löytää hetkessä kaikki virheet!
Jostain syystä 15x15 ruudukosta jää tällä yksinkertaisella satunnaisohjelmalla täyttämättä aina kaksi ruutua. Onnistuuko täyttö paremmalla ohjelmalla? Vai onko mahdotonta?
Palstan matemaatikoille hiukan haastetta täyttää koko ruudukko aivan täyteen kahdella eri merkillä (värillä). Minkään neliön kaikissa neljässä nurkassa ei saa olla samaa merkkiä.
Täytin 14x14 ruudukon täysin satunnaisesti. Helppo löytää useita erilaisia. Jos johonkin ruutuun ei pystytty lisäämään kumpaakan merkkiä, jokaisesta jumittavasta neliöstä poistettiin satunnaisesti yksi kolmesta nurkasta ja ruutuun laitettiin merkki, jota oli vähiten. Täytettyjen merkkien määrä pienenee aina jumitilanteissa useallakin merkillä, mutta aina pääsee jatkamaan uudesta (toivottavasti) erilaisesta (?) tilanteesta. Max yrityksen jälkeen luovutaan ja aloitetaan alusta.
0 1 0 1 1 1 0 0 0 1 1 0 1 0
0 1 1 1 0 0 1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0 1 1 1 1 0 1
0 0 0 1 1 1 1 0 0 1 0 1 0 0
0 1 0 0 1 0 1 0 1 0 0 1 1 0
1 0 0 1 0 0 1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1 0 0 0 1 0 1
1 0 1 0 0 0 1 0 0 1 1 1 1 1
1 1 0 0 1 1 1 1 0 0 1 0 0 1
0 1 1 0 0 1 0 1 0 1 0 0 1 0
0 0 1 0 1 0 0 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 1 0 0 0 1 1
0 0 0 1 0 1 0 1 0 0 1 1 1 0
1 1 0 1 1 0 0 0 0 1 1 0 1 0
196 98 98
Täytetystä 14x14 ruudukosta voi valita eri tavoin useita pienempiä täytettyjä ruudukoita. Valitkaa vaikka joku 4x4 tai 5x5 alue ja hakekaa siitä virhe. Jos ette löydä virhettä, yrittäkää uudestaan tai tehkää ohjelma joka löytää hetkessä kaikki virheet!
Jostain syystä 15x15 ruudukosta jää tällä yksinkertaisella satunnaisohjelmalla täyttämättä aina kaksi ruutua. Onnistuuko täyttö paremmalla ohjelmalla? Vai onko mahdotonta?
Vastaukset 4
Vanhimmat
Täytäpä miljardi x miljardi- ruudukko ja laita se jonnekin näkösälle, eikä tuommosta pikkupelleilyä.
15x15 ruudukossa on 1015 neliötä. Jos ruudukko on 225-bittinen binääriluku, niin minkään neliön nurkkabittien summa ei saa olla nolla tai neljä.
Vastaesimerkin löytäminen lienee helpoin tapa. Saattaa onnistua lajittelemalla neliölista yhteisten nurkkien määrien perusteella. Listan alkuun yhteisiä nurkkia yhteensä eniten omaavat neliöt ja jokaisen neliön nurkkalistaan alkuun parhaat ruudut. Tuosta voi sitten jakaa vuorotellen jokaisesta neliöstä yhden nurkan molemmille merkeille ja toivoa, ettei jäljelle jäisi yhtään täyttämätöntä ruutua sotkemaan kaikkea.
[106, [112, 128, 127, 113]]
[106, [112, 127, 126, 111]]
[106, [112, 113, 98, 97]]
[106, [112, 111, 97, 96]]
[104, [128, 126, 98, 96]]
[100, [128, 127, 143, 142]]
...
[58, [28, 29, 14, 13]]
[58, [16, 224, 211, 29]]
[58, [16, 15, 1, 0]]
[56, [224, 210, 14, 0]]
Alussa neliön yhteisten nurkkien määrä (106,...,56). Viimeisenä näyttäisi olevan suurin eli 15 sivuinen neliö.
Tein yksinkertaisen nopean ohjelman, joka hakee kaikki vaihtoehdot binäärilukuina. Ohjelma muodostaa kaikki neliöt ja lajittelee ne siten, että ensimmäisenä listassa on neliö, jonka vähiten merkitsevä nurkkabitti (oikea alanurkka) on suurin. Jos on samoja, niin pienin neliö aina ensin.
Aloitetaan luvusta nolla ja tarkistetaan nurkkalistan avulla onko luku oikein. Jos on virhe, lisätään vähiten merkitsevää nurkkabittiä vastaava luku ja aloitetaan alusta. Luku kasvaa maksimaalisen nopeasti. Mikään ratkaisu ei jää havaitsematta. Aina kun löytyy ratkaisu, lukuun lisätään 1.
Ohjelma tutkii yksinkertaisella xor-operaatiolla, mikä on suurin muuttunut bitti luvussa ja laskee siitä taulukon avulla, mistä kohtaa neliölistaa aloitetaan. Koska nurkkalistan alkupäässä on isoimmat bitit (oikeat alanurkat), ei niitä tarvitse käydä uudestaan läpi, ellei mitään muutoksia luvun eniten merkitsevässä päässä ole tapahtunut. Valtava nopeutus.
Isoilla ruudukoilla luku kasvaa usein jopa yli triljoonan triljoonan hyppäyksin. Ja tietysti sitä nopeammin, mitä vähemmän ratkaisuja löytyy.
Kun sain selville ratkaisujen tarkat määrät (ja kerroin ne kahdella), niin Google löysi heti oeis.org:sta:
https://oeis.org/A018803
Tuolta selviää, ettei 15x15 ruudukolle löydy yhtään ratkaisua.
Ongelmaa yritettiin ratkaista 30 vuotta sitten:
https://groups.google.com/g/sci.math/c/itKRTnk7sVA
Tämä on ihan perusmatematiikkaa. Monet miljoonat vastaavat käytännön ongelmat kemiassa, materiaalifysiikassa ja geenitekniikassa ovat monta pykälää hankalampia ja vaikeampia ja usein kolmiulotteisia.
Taulukosta 12 nähdään miten 12x12 ruudukon ratkaisujen määrät romahtavat lähes nollaan (verrattuna 2^144:ään). Ei löydy enää montaakaan erilaista 12-bittistä neliön sivua. Tätä tietoa voi hyödyntää 13x13 ruudukoiden laskennassa. Sen ylärivissähän on oltava kaksi 12-bitin sivua. Myös takaperin katsottuna.
n
2: ___________14
3: __________276
4: ________10980
5: _______781712
6: _____58339148
7: ___3066831440
8: __58170992144
9: _313031791856
10: 109957124552
11: __5020721992
12: _____3980056
13: _____1140264
14: ______232228
15: ___________0
14x14 ruudukoissa on vain 32 erilaista 14-bittistä sivua. Niistä saadaan kombinoitua vain 16 laillista 15-bittistä sivua ja vain kahdeksan 0:lla alkavaa yläsivua (yläriviä). Vaihtoehdot karsiutuvat 1/2000-osaan. Ratkaistuja 14x14-ruudukoita voi myös yrittää täydentää kaikilla laillisilla 14-bitin sivuilla ensin 15x14-suorakaiteeksi. Edes tämä ei taida onnistua koskaan.