Aapo Rantalainen's blog

Experiences with Information Technology and Open source

Tikkupeli ja matematiikkaa.

Posted by Aapo Rantalainen on August 15, 2013

Kumpi voittaa 7531-tikkupelin? Miksi?
Säännöt kahdelle pelaajalle.
Alkuasetelma: Tikut ovat riveittäin, ensimmäisellä rivillä 7 tikkua, seuraavalla 5, sitten 3 ja viimeisellä 1.

Vuorollaan pelaaja valitsee yhden rivin ja poistaa siltä haluamansa määrän tikkuja. Kuitenkin ainakin yhden. Halutessaan vaikka kaikki (eikä tietenkään enempää kuin mitä rivillä on).

Häviäjä on se pelaaja joka joutuu ottamaan pelilaudalta viimeisen tikun.

Saanko aloitusvuoron vai haluatko sinä aloittaa pelin? Todista.

alkutila

Pysähdy tähän miettimään.

Vastaus alkaa:

Otetaan käyttöön merkintätapa, jossa jokainen pelitilanne kuvataan neljällä numeromerkillä. Koska tikkurivien järjestyksellä ei ole merkitystä, sovitaan että numeromerkit ovat aina suurimmasta pienimpään. Eli tila 2100 = 2010 = 2001 = 1200 = 1020 = 0120 = 0210 = 0201 = 0021. Merkitään näitä kaikkia tiloja 2100:lla
Nyt pelin häviämisehto on:

Määritelmä I
Pelaaja häviää jos hänelle tulee tila 1000.
(Reunahuomautus: Jos jättäisimme nollat kokonaan merkitsemättä, tikkurivien määrä aloituksessa voisi olla jokin muukin kuin neljä.)

Tässä seuraa matemaattinen todistus. ‘Lemma’ on siis ‘apulause’. Koodarit voi ajatella sen funktiokutsuna (älä sotke matematiikan funktioihin). Määrittelen aina ensin lemman, ennen kuin käytän sitä, jotta ei varmasti synny kehäpäätelmiä.

Väitän että aloittaja häviää aina (tämä selviää todistuksen lopusta vasta).
Väite: Kaikille (eli ∀) aloittajan siirroille löytyy (eli ∃) vastustajalta vastine, jolla aloittaja häviää.

Lemma 1110: vuorossa oleva pelaaja häviää, jos hänelle tulee tila 1110.
Todistus: Tekee pelaaja minkä tahansa siirron, niin seuraava tila on 1100.
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 2200: häviää
Todistus: (Pelaaja voi ottaa jommalta kummalta riviltä joko yhden tai kaksi tikkua.)
Voi päätyä tilaan
a) 2100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.
b) 2000
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 2211: häviää
Todistus: Voi päätyä tilaan
a) 2210
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
b) 2111
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
c) 2110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.

Lemma 3210: häviää
Todistus: Voi päätyä tilaan
a) 3200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
b) 3110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
c) 2210
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
d) 2110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
e) 2100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 3300: häviää
Todistus: Voi päätyä tilaan
a) 3200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
b) 3100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.
c) 3000
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 3311: häviää
Todistus: Voi päätyä tilaan
a) 3310
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
b) 3211
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
c) 3111
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
d) 3110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.

Lemma 4400: häviää
Todistus: Voi päätyä tilaan
a) 4300
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
b) 4200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
c) 4100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.
d) 4000
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 4411: häviää
Todistus: Voi päätyä tilaan
a) 4410
Josta vastustaja palauttaa 4400. Lemman 4400 mukaan häviää.
b) 4311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
c) 4211
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
d) 4111
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
e) 4110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.

Lemma 5500: häviää
Todistus: Voi päätyä tilaan
a) 5400
Josta vastustaja palauttaa 4400. Lemman 4400 mukaan häviää.
b) 5300
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
c) 5200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
d) 5100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.
e) 5000
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 5410: häviää
Todistus: Voi päätyä tilaan
a) 5400
Josta vastustaja palauttaa 5500. Lemman 5500 mukaan häviää.
b) 5310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
c) 5210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
d) 5110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
e) 5100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.
f) 4410
Josta vastustaja palauttaa 4400. Lemman 4400 mukaan häviää.
g) 4310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
h) 4210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
i) 4110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
j) 4100
Josta vastustaja palauttaa 1000. Määritelmän mukaan häviää.

Lemma 5511: häviää
Todistus: Voi päätyä tilaan
a) 5510
Josta vastustaja palauttaa 5500. Lemman 5500 mukaan häviää.
b) 5411
Josta vastustaja palauttaa 4411. Lemman 4411 mukaan häviää.
c) 5311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
d) 5211
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
e) 5111
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.
f) 5110
Josta vastustaja palauttaa 1110. Lemman 1110 mukaan häviää.

Lemma 6420: häviää
Todistus: Voi päätyä tilaan
a) 6410
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
b) 6400
Josta vastustaja palauttaa 4400. Lemman 4400 mukaan häviää.
c) 6320
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
d) 6220
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
e) 6210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
f) 6200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
g) 5420
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
h) 4420
Josta vastustaja palauttaa 4400. Lemman 4400 mukaan häviää.
i) 4320
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
j) 4220
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.
k) 4210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
l) 4200
Josta vastustaja palauttaa 2200. Lemman 2200 mukaan häviää.

Lemma 6431: häviää
Todistus: Voi päätyä tilaan
a) 6430
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
b) 6421
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
c) 6411
Josta vastustaja palauttaa 4411. Lemman 4411 mukaan häviää.
d) 6410
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
e) 6331
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
f) 6321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
g) 6311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
h) 6310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
i) 5431
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
j) 4431
Josta vastustaja palauttaa 4411. Lemman 4411 mukaan häviää.
k) 4331
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
l) 4321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
m) 4311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
n) 4310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.

Lemma 6521: häviää
Todistus: Voi päätyä tilaan
a) 6520
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
b) 6511
Josta vastustaja palauttaa 5511. Lemman 5511 mukaan häviää.
c) 6510
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
d) 6421
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
e) 6321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
f) 6221
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
g) 6211
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
h) 6210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
i) 5521
Josta vastustaja palauttaa 5511. Lemman 5511 mukaan häviää.
j) 5421
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
k) 5321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
l) 5221
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
m) 5211
Josta vastustaja palauttaa 2211. Lemman 2211 mukaan häviää.
n) 5210
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.

Lemma 6530: häviää
Todistus: Voi päätyä tilaan
a) 6520
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
b) 6510
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
c) 6500
Josta vastustaja palauttaa 5500. Lemman 5500 mukaan häviää.
d) 6430
Josta vastustaja palauttaa 6420. Lemman 6420 mukaan häviää.
e) 6330
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
f) 6320
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
g) 6310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
h) 6300
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
i) 5530
Josta vastustaja palauttaa 5500. Lemman 5500 mukaan häviää.
j) 5430
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
k) 5330
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.
l) 5320
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
m) 5310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
n) 5300
Josta vastustaja palauttaa 3300. Lemman 3300 mukaan häviää.

VÄITE: Tilanteesta 7531 häviää.
Todistus: Voi päätyä tilaan
a) 7530
Josta vastustaja palauttaa 6530. Lemman 6530 mukaan häviää.
b) 7521
Josta vastustaja palauttaa 6521. Lemman 6521 mukaan häviää.
c) 7511
Josta vastustaja palauttaa 5511. Lemman 5511 mukaan häviää.
d) 7510
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
e) 7431
Josta vastustaja palauttaa 6431. Lemman 6431 mukaan häviää.
f) 7331
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
g) 7321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
h) 7311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
i) 7301
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
j) 6531
Josta vastustaja palauttaa 6431. Lemman 6431 mukaan häviää.
k) 5531
Josta vastustaja palauttaa 5511. Lemman 5511 mukaan häviää.
l) 5431
Josta vastustaja palauttaa 5410. Lemman 5410 mukaan häviää.
m) 5331
Josta vastustaja palauttaa 5511. Lemman 5511 mukaan häviää.
n) 5321
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.
o) 5311
Josta vastustaja palauttaa 3311. Lemman 3311 mukaan häviää.
p) 5310
Josta vastustaja palauttaa 3210. Lemman 3210 mukaan häviää.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: