Erityisen matriisin olemassaolo

matriisilaskija

Mitenkä tallainen tehtävä ratkaistaan? 5x4-matriisin alkiot ovat kokonaislukuja väliltä 0,...,9. Siitä muodostetaan lukuja valitsemalla jokin numero ensimmäiseksi, valitsemalla jokin kahdeksasta suunnasta ja kuljetaan sitä pitkin niin paljon kuin halutaan. Esimerkiksi matriisista

1244
2343
1233
3464
6576

voi lukea vaikkapa luvut 1334, 2343, 266, mutta 264:ää ei, sillä lukiessa jouduttaisiin kääntymään. Miten osoitetaan, että matriisin 20-numeroa voidaan valita siten, että siitä voi lukea lukujen 0,...,20 neliöt?

4

60

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Brute Force

      Tällainen tehtävä osoitetaan konstruktivistisesti. Eli teet sellaisen 5x4 matriisin joka koostuu luvuista 0,...,9 ja ympyröit vaikkapa lukujen 0,...20 neliöt.

      Kannattanee ympyröinti suorittaa selvyyden vuoksi useampaan eri matriisiin (sama matriisi mutta uusiksi kirjoitettuna)

      Jos taas pitäisi osoittaa että ei ole mahdollista niin homma on vaikeampi.
      Se voitaisiin ohjelmoida tietokoneelle periaatteessa joka tutkisi kaikki 10^20 matriisia (tai itse asiassa alle) ja todeta ettei löytynyt ehdot täyttäviä matriiseja. Aikaa kuluisi tuhottomasti, mutta perustelu olisi riittvä.

    • matriisilaskija

      Ookei. Mulla taitaa olla hidas algoritmi kun en löydä kyseistä matriisia.

    • MattiKSinisalo

      Tässäpä esimerkkiratkaisu:

      1,5,3,1
      4,2,6,0
      4,9,1,0
      1,4,8,4
      6,5,2,2

    • matriisilaskija

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Mihin Ilkka Kanerva kuoli?

      Kun näin jokin aika sitten kuvan riutuneen näköisestä Kanervasta, sanoin vaimolle että haimasyövältä vaikuttaa. Vaimon isä oli kuollut kyseiseen tauti
      Maailman menoa
      277
      17688
    2. Oho! Susanna Laine uudessa hiustyylissä - Julkkismeikkaajalta tiukka palaute: "Ihan sama..."

      Ex-Salkkarit tähti ja juontaja Susanna Laine on monessa mukana. Ex-missi tunnetaan pitkistä, vaaleista hiuksistaan . Mitäs tykkäät uudesta hiustyylist
      Kotimaiset julkkisjuorut
      24
      5676
    3. Ilkka kanerva

      Ilkka Kanerva kuollut 74v
      Turku
      123
      2642
    4. Yllätyspaljastus: Poppari Robin Packalen kiittää urastaan iskelmätähti Juha Tapiota: "Jos mä en..."

      Oi, mikä tarina. Juha Tapio ja Robin ovat kyllä symppiksiä molemmat. Kumpi heistä on suosikkisi? https://www.suomi24.fi/viihde/yllatyspaljastus-poppar
      Kotimaiset julkkisjuorut
      17
      2162
    5. Venäjän lippulaiva Moskva upotettu Mustallamerellä

      Venäjän laivaston lippulaiva Mustalalmerellä on 180 m pituinen, Neuvostoliiton aikana rakennettu Moskva-niminen risteilijä. Ukraina ilmoitti eilen saa
      Maailman menoa
      336
      1795
    6. Pikkaraiskan puhelut

      Mitä tuo jätkä hakee sillä että julkaisee kuinka kauan on puhunut puhelimessa? Tekee itsestään vieläkin idiootimman tuolla vai mikä tää juttu?
      Kotimaiset julkkisjuorut
      111
      1047
    7. Ilkka Kanerva on kuollut

      74-vuotiaana.
      Maailman menoa
      59
      973
    8. Hossein Najaf juotti lapset humalaan ja käytti häikäilemättä hyväkseen

      Keski-Suomen käräjäoikeus on tuominnut 60-vuotiaan Hossein Najafin neljän vuoden vankeusrangaistukseen. Ensimmäisen tytön kanssa hän oli useita kerto
      Maailman menoa
      32
      941
    9. Sofia Belorf ja Sonja Aiello

      Viihtyvät yhdessä dinnerillä. Pienet piirit. Mitä ajatuksia herättää ?
      Kotimaiset julkkisjuorut
      45
      941
    Aihe