NxN ruudukon täyttö kahdella eri merkillä niin, ettei muodostu neliöitä

Anonyymi

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?

4

300

Äänestä

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • 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ä.

    Takaisin ylös

    Luetuimmat keskustelut

    1. Yritystuet 10 mrd. vuodessa, eli yrittäjäriski valtiolla kuten kommunismissa

      Pelkästään Viking Linen viinanhakuristeilyitä sponsoroidaan 20 miljoonalla eurolla vuosittain. Dieselin verotukikin on
      Yrittäjyys
      113
      9451

    2. Pystyisitkö pitämään

      Näppejä erossa jos tulisi siihen tilaisuus
      Ikävä
      92
      9051

    3. Oikeistolainen luki Med mod att leda : en biografi

      ...ei tykänny Sanna Marinista
      Maailman menoa
      18
      7855

    4. Sture Fjäder haluaa tuensaajien nimet julki

      Kokoomuspoliitikko haluaa yli 800 euroa kuukaudessa tukia saavien nimet julki. Ehkä olisi syytä julkaista myös kuvat? h
      Maailman menoa
      177
      6254

    5. Luotathan siihen tunteeseen, joka välillämme on?

      Uskothan myös, että se kestää tämän? Kaipaan sinua valtavasti. Vielä tehdään yhdessä tästä jotain ihmeellistä ja kaunist
      Ikävä
      58
      5378

    6. Sannan kirja USA:n bestseller!

      "Congratulations to Sanna Marin's HOPE IN ACTION, officially a USA TODAY bestseller!" Kertoo Scribner. Mitäs persut tä
      Maailman menoa
      25
      4999

    7. Onnettomuus

      Hukkajärventiellä kolaroi lavetti ja henkilöauto. Uutista ei missään! Hys hys ollaanko hiljaa tästäkin?
      Kuhmo
      8
      4428

    8. En saa sua mielestäni vaikka tekisin mitä

      Mikä tähän auttaa.. ei mikään. Edes aika. Kaivan sut kohta vaikka kivenkolosta että saan kysyä haluatko sinäkin💛
      Ikävä
      23
      4345

    9. Milloin viimeksi näit kaivattusi?

      Toimisitko nyt toisin kuin siinä tilanteessa teit?
      Ikävä
      38
      4243

    10. Tuntuuko ettet tiedä

      Enää miten toimia mun suhteen. Kun en taida tietää itsekään
      Ikävä
      39
      4173
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt