Viikon 13 aiheena on lukuteoria ja peliteoria. Kolme ensimmäistä tehtävää käsittelevät lukuteoriaa ja loput kolme peliteoriaa. KKKK luvut 21 ja 25 käsittelevät näitä aiheita.
Neliösumma
[hint]Laske ensin kaikki kahden neliön summat[/hint]
Numeropeli
[hint]Laske jokaiselle tilalle kumpi voittaa pelin[/hint]
Tikkupeli
[hint]Tikkupeli tunnetaan paremmin nimellä nim-peli[/hint]
Uolevinolla
[hint]Pelilssä on 2^16 tilaa. Laske jokaiselle tilalle tilan nim-luku[/hint]
Spoilerit:
- Rinkelit
Jos jana osuu pisteeseen (x0+a, y0+b) se osuu kaikkiin pisteisiin (x0+ca, y0+cb). Lisäksi, jos ensimmäisen pisteen luvut a ja b ovat suhteellisia alkulukuja, suora ei osu niiden välissä yhteenkään muuhun pisteeseen.
Näin ollen pisteiden x- sekä y-koordinaattien erotusten suurin yhteinen tekijä kertoo monta rinkeliä pisteiden välissä on (loppupiste mukaan luettuna).
- Uusi tehtävä
Käytä summan laskukaavaa. Muista käyttää jakaessa käänteislukua (modular inverse)
- Neliösumma
Summan voi laskea kahdessa osassa jotka ovat kumpikin kahden neliön summia. Kaikki kahden neliön summat voi laskea etukäteen, jonka jälkeen voidaan etsiä kaksi kahden neliön summaa joista saadaan koko (neljän neliön) summa.
- Numeropeli
Jos luku on 10:llä jaollinen, kyseessä on häviötila
- Tikkupeli
Uolevin valinnan jälkeen pelataan tavallinen Nim-peli, eli Uolevin pitää valita kasojen xor-summaksi 0. Välit joiden xor-summa on 0 voi löytää niin, että käy läpi taulukkoa vasemmalta oikealle pitäen yllä xor-summaa. Jos kyseinen xor-summa on löytynyt aiemmin kohdassa i, niin väli i+1:stä tähän asti on sopiva väli.
- Uolevinolla
Jokaisessa ruudukossa on 2^16 erilaista tilannetta, eli ne voi kaikki käydä läpi.
Tässä muutetaan peli ensin Nim-peliksi, ja ratkaistaan se tavallisesti. Lasketaan jokaiselle ruudukon mahdolliselle tilanteelle Nim-luku. Jos tilanteessa on neljän suora, niin Nim-luku on 0. Muutoin nim-luku on pienin kokonaisluku jota ei esiinny missään ruudukon tilanteessa johon pääsee lisäämällä yhden nollan ruudukkoon. Esimerkiksi jos tilanteesta voidaan pelata tilanteisiin joiden nim-luvut ovat {0, 1, 3, 1, 5, 5, 0, 1}, niin sen tilanteen nim-luku on 2.
Tämän jälkeen lasketaan ruudukoiden nim-luvuista xor-summa.