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?
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?
Vastaukset 4
Vanhimmat
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ä.
Ookei. Mulla taitaa olla hidas algoritmi kun en löydä kyseistä matriisia.
Tässäpä esimerkkiratkaisu:
1,5,3,1
4,2,6,0
4,9,1,0
1,4,8,4
6,5,2,2
OK. Taitaa toimia. Olisi kiinnostavaa tietää, millaisella algoritmilla löysit ratkaisun? Löysin probleeman osoitteesta http://stackoverflow.com/questions/3382859/solving-a-recreational-square-packing-problem ja päätin tutkia joitain pienempiä tapauksia ensin. Myös alkuperäinen ongelma on ratkeamatta.