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
274
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
Poliisi: Kymmenhenkinen pohjalaisperhe ollut vuoden kateissa kansainvälinen etsintäkuulutus Poliis
Poliisi: Kymmenhenkinen pohjalaisperhe ollut vuoden kateissa – kansainvälinen etsintäkuulutus Poliisi pyytää yleisön apu2722410Tässä totuus jälleensyntymisestä - voit yllättyä
Jumalasta syntyminen Raamatussa ei tässä Joh. 3:3. ole alkukielen mukaan ollenkaan sanaa uudestisyntyminen, vaan pelkä2991299- 1081201
En kadu sitä, että kohtasin hänet
mutta kadun sitä, että aloin kirjoittamaan tänne palstalle. Jollain tasolla se saa vain asiat enemmän solmuun ja tekee n831201Oisko mitenkään mahdollisesti ihan pikkuisen ikävä..
...edes ihan pikkuisen pikkuisen ikävä sulla mua??.. Että miettisit vaikka vähän missähän se nyt on ja oiskohan hauska n581155Noniin rakas
Annetaanko pikkuhiljaa jo olla, niin ehkä säilyy vienot hymyt kohdatessa. En edelleenkään halua sulle tai kenellekään mi811096- 44962
Helena Koivu : Ja kohta mennään taas
Kohta kohtalon päivä lähestyy kuinka käy Helena Koivulle ? Kenen puolella olet? Jos vastauksesi on Helenan niin voisi67897Au pair -työ Thaimaassa herättää kiivasta keskustelua somessa: "4cm torakoita, huumeita, tauteja..."
Au pairit -sarjan uusi kausi herättää keskustelua Suomi24 Keskustelupalvelussa. Mielipiteitä ladataan puolesta ja vastaa22860- 33767