Tervepä terve! Koittaa jälleen se hetki viikosta kun paljastetaan menneen jakson pulmat, ja aletaan nakertaa uutta pähkinää... ;)
Hessu tienasi peräti 10 tähteä, mikä taisi olla hänen uusi ennätyksensä... Onnittelut!
Muistutus: Jos joku haluaa järkätä omat Viikon Pulmansa (TM), omanlaisine tehtävineen, se olisi hyvä idea!
Ratkaisut:
Huom! a (mod n) luetaan 'a:n jakojäännös n:llä jaettaessa'.
1 tähti *: Löydä ja todista numeerinen arvo seuraavalle: 1 2/(1 2/(1 2/(1 2/(1 ...
Ratkaisu: Hessu hoksasi niksin: Luku toteuttaa toisen asteen yhtälön x = 1 2/x . Ainoa positiivinen ratkaisu on x=2.
2 tähteä **: Seitsemän erilaisen positiivisen kokonaisluvun summa on 100. Osoita, että niistä joidenkin kolmen summa on ainakin 50.
Ratkaisu: Hessu keksi tämänkin. Eli järjestetään luvut x_1
Hessu tienasi peräti 10 tähteä, mikä taisi olla hänen uusi ennätyksensä... Onnittelut!
Muistutus: Jos joku haluaa järkätä omat Viikon Pulmansa (TM), omanlaisine tehtävineen, se olisi hyvä idea!
Ratkaisut:
Huom! a (mod n) luetaan 'a:n jakojäännös n:llä jaettaessa'.
1 tähti *: Löydä ja todista numeerinen arvo seuraavalle: 1 2/(1 2/(1 2/(1 2/(1 ...
Ratkaisu: Hessu hoksasi niksin: Luku toteuttaa toisen asteen yhtälön x = 1 2/x . Ainoa positiivinen ratkaisu on x=2.
2 tähteä **: Seitsemän erilaisen positiivisen kokonaisluvun summa on 100. Osoita, että niistä joidenkin kolmen summa on ainakin 50.
Ratkaisu: Hessu keksi tämänkin. Eli järjestetään luvut x_1
Vastaukset 5
Vanhimmat
"Olkoon x_1, x_2, ..., x_6 mikä tahansa sekvenssi. Väitämme, että luku s(x_1) = 2x_1 4x_2 ... 12x_7 (mod 10) on sama kaikille jonon sekvensseille."
Pitäisikö tuon olla 2x_1 4x_2 ... 14x_7?
Mistä tuo invarianttius "huomataan"?
Mistä tällaisia invariantti-tehtäviä löytäisi lisää? En tahdo saada intuitiivista otetta ja muutama erittäin yksinkertainen harjoitus voisi avata pari lukkoa (tästä olisi hyötyä algoritmien todistamisessa).
PS: Suomessa ei ole tapana sanoa "olemme valmiita" (we're done), vaan esim. "ja väite on todistettu".
"Olkoon x_1, x_2, ..., x_6 mikä tahansa sekvenssi. Väitämme, että luku s(x_1) = 2x_1 4x_2 ... 12x_7 (mod 10) on sama kaikille jonon sekvensseille. "
"s(1,0,1,0,1,0) = 6"
Mitä tuossa tapahtuu? Ensin määritellään funktio s, joka saa argumentikseen yhden reaaliluvun. Sitten yhtäkkiä s lasketaan kuudesta luvusta.
Siinä oli pikku näppäilyvirhe: viimeisen termin piti olla 12x_6.
No varmaankin kannattaa kokeilla erilaisia muunnoksia tehtävän rekursiivisesta säännöstä. Eli ei niin sanoutusti mennä merta edemmäs kalaan! x_1 ... x_6 (mod 10) ei selvästikään ollut invariantti, mutta haluaisimme jotenkin muuttaa/käyttää sitä niin, että se olisi peräkkäisille sekvensseille sama.
Eli haluamme a_1*x_2 a_2*x_3 ... a_6*x_7 - (a_1*x_1 ... a_6*x_6) = 0 (mod 10) ja tiedämme myös, että x_7 = x_1 ... x_6 (mod 10). Pienellä tuijottelulla ja kokeilulla saamme ratkaisun.
Ja näin olemmekin valmiita! :)
... notaation väärinkäyttö, eli ideana ei niinkään ollut funktion 'argumentit', vaan se että jokaisen sekvenssin alkutermi on tavallaan kirjanmerkkinä. Muuten minun olisi erikseen pitänyt selventää, että sekvenssit ovat peräkkäisiä... Onhan tuo noinkin oikein määritelty, kunhan käytämme merkintää
s(x_i) = x_i x_(i 1) ... x_(i 5) (mod 10).
Tässä siis x_i = jonon i:s termi.
... voi etsiä ihan googlettamallakin. Hedelmällinen haku on esim. 'problem solving course'. Pulmia löytyy esim. kirjasta 'Bollobas: Coffee Time In Memphis' tai 'Mathematical Olympiad Challenges'.
Muutamia tehtäviä:
http://www.jstor.org/view/0025570x/di021154/02p0170m/0
http://www.mscs.dal.ca/~hoshino/2790.html
Ymmärrän kyllä intosi löytää ihan puhtaasti invariantti-ongelmia -- ratkaisut ovat ehkäpä kauneimpia mitä maa päällään kantaa. Silti en ole löytänyt mitään yhtä lähdettä niille. (Jos joku tietää sellaisen, minä olen kiinnostunut!) Jonain päivänä aion julkaista kokoelman pelkkiä invariantti-ongelmia!
Ensimmäiseksi invariantti-harjoitukseksi suosittelen todistamaan jonkinlaisen osaratkaisun uudesta 5 tähden tehtävästä: Lähinnä sen, että 8|mn . Sen jälkeen voit koettaa 4 tähden tehtävää hieman samantyylisesti, mutta kehittyneemmällä invariantilla.