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?
NxN ruudukon täyttö kahdella eri merkillä niin, ettei muodostu neliöitä
4
291
Vastaukset
- Anonyymi
Täytäpä miljardi x miljardi- ruudukko ja laita se jonnekin näkösälle, eikä tuommosta pikkupelleilyä.
- Anonyymi
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ö. - Anonyymi
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- Anonyymi
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.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Purran tuhoja tuskin saadaan koskaan korjatuksikaan
Purra on aiheuttanut Suomen taloudelle karmaisevat tuhot. Sen lisäksi Purra on ajanut myös suuren osan Suomen kansasta k1527890Miksi persuilla ei ole firmoja?
Kuten vasemmisstolaisilla, esim. Sannalla MA\PI. Eikö ole aika erikoista?1017327Persut hommasivat Suomeen 35 000 pientä lasta v. 2015
Onko Riikka Purra nyt tavoittelemassa tätä samaa historiallista persujen utopiaa? Purram kaksinaamaisessa pelissä vaadit317212Se oli Orpo joka rynni Eagle S -alukselle
Vastoin kaikkia kansainvälisen merenkäynnin sääntöjä. Kunpa olisi ollut purjehtija Harkimo Suomen johdossa silloin. ht27186Aamun Riikka: työttömyydessä lähestytään viime laman synkintä vaihetta
Nopeasti mentiiin upean Marinin hallituksen ennätystyöllisyydestä toiseen ääripäähän, kohti Suomen historian kurjimpia t216928Marinin tuhojen korjaaminen kestää kahdeksan vuotta
Nyt on vasta neljännes mennyt ja ensimmäiset korjausliikkeet saatu liikkeelle. Innokkaimmat olivat odottaneet että jo t756374Miksette persut irtisanoudu Kirkin lausunnoista?
Kirkhän muun muassa vaati raiskattuja naisia pidättäytymään abortista ja vaimoja alistumaan aviomiestensä tahtoon. Mik1126262Purran vuoro kiihoittua Lepomäen sääristä
"Ulkoministeri Elina sanoo, ettei muuta pukeutumistaan sen mukaan, kenet tapaa, ja että hän ei suostuisi peittämään kasv236174Persujen kaksoisstandardit: Räsäsen uhkailu paha, Virran uhkailu hyvä
Tässä taas nähdään kuinka kaksinaamaista porukkaa persut ovat. Mitäs persut tähän?475478Demarikultin uhri kertoo
Demarikultin uhri kertoo: “En saanut mennä edes suihkuun ilman lupaa” – Seksuaalisen hyväksikäytön uhri kertoo vuosistaa845390