Tässä tulee jälleen edellisen jakson ratkaisut sekä uudet Pulmat.
Zäki keräsi 10 tähteä ja Hessu 4.5 tähteä. Onnittelut!
Ratkaisut:
1 tähti *: Olkoon shakkilaudan koko n*n, missä n on pariton. Voiko ratsu tehdä seuraavan reissun: Se lähtee jostakin ruudusta liikkeelle, käy kaikissa muissa ruuduissa tasan kerran ja palaa lopussa lähtöruutuun takaisin?
Ratkaisu: Zäki ja Hessu löysivät jujun: Ratsu vaihtaa ruudun väriä joka hypyllä, joten ainoastaan parillinen määrä siirtoja voi johtaa alkuruudun väriin. Siksi kierros on mahdoton.
2 tähteä **: Miehellä on 2 euroa, mutta tarvitsee 10 euroa lempikirjaansa. Hän uhkapelaa rahojaan pelissä, jossa heitetään tasapuolista kolikkoa: kruunan sattuessa panos kaksinkertaistetaan, muuten panos menetetään. Mies pelaa toistuvasti seuraavalla taktiikalla: jos rahaa on alle kuusi euroa, hän laittaa kaiken peliin. Jos rahaa on enemmän, hän pelaa juuri niin paljon, että hänellä on voiton sattuessa tasan 10 euroa. Millä todennäköisyydellä mies onnistuu tavoitteessaan?
Ratkaisu: Hessu löysi ratkaisun. Peruskoululaiselle ja jopa useimmille lukiolaisille tehtävä voisi tuottaa ongelmia, sillä on olemassa mm. ääretön rahaketju 2-->4-->8-->6-->2-->4-->...
Kuvan piirtäminen auttaa. Merkitään p_i = P(voitto tulee jos aloitamme rahasumma i). Selvästikin p_2 = (p_4)/2, p_4 = (p_8)/2, p_8 = (p_6)/2 1/2, p_6 = (p_2)/2 1/2. Sijoittamalla nämä takaisin käänteisessä järjestyksessä, saamme yhtälön p_2 suhteen, josta voi ratkaista p_2 = 1/5.
Ratkaisua voi lyhentää, jos huomaamme, että kuva on symmetrinen niin että p_8 = 1-p_2. Hessu myös mietti, josko tehtävän voisi ratkaista huomaamalla, että peli on reilu (ajatellen sitä kahden hengen pelinä, jossa toisella pelaajalla on aluksi 8 euroa). Mutta peli on reilu joss p_2 = 1/5. Sen me juuri osoitimme! Ei ole mielestäni täysin selvää ensisilmäyksellä, että peli on välttämättä reilu, mutta tämän yksittäisen esimerkin symmetria mahdollistaa sen.
3 tähteä ***: Shakkilaudan koko on n*n. Osa ruuduista on valmiiksi saastuneita. Seuraavassa vaiheessa kaikki ne puhtaat ruudut saastuvat, joilla on vähintään kaksi saastunutta naapuria. Sama jatkuu, kunnes kaikki ruudut ovat saastuneita, tai viruksen leviäminen loppuu. Mikä on minimimäärä alkuperäisiä saastuneita ruutuja, jotta kaikki ruudut saastuisivat lopulta?
Ratkaisu: Hessu huomasi, että n ruutua riittävät, ja että leviäminen pysähtyy kunhan päädymme umpinaisiin suorakulmioihin, jotka ovat vähintään kahden ruudun päässä toisistaan vaaka- tai pystysuunnassa. Tästä hyvästä 1.5 tähteä hänelle. Hän yritti myös perustella, miksi n ruutua tarvitaan, mutta ratkaisuyritys ei täysin vakuuttanut aukottomuudellaan tai selkeydellään.
Tässä hämäävän helppo ratkaisu: Saastuneen alueen yhteenlaskettu ympärysmitta ei koskaan pienene. Kun koko lauta on saastunut, ympärysmitta on 4n. Siispä tarvitsemme ainakin n alkuperäisiä saastuneita ruutuja. Tuo määrä myös riittää: saastuta alussa lävistäjä.
4 tähteä ****: Osoita, että viisi väriä riittää värittämään minkä tahansa paperille piirrettävän kartan, niin että vierekkäisillä alueilla on eri värit.
Vihje: Voit olettaa, että jos tasoon piirrettävässä graafissa on n solmukohtaa ja m kaarta, silloin m on korkeintaan 3n-6.
1 bonustähti: Todista vihje.
10^500 bonustähteä: Osoita, itse keksimälläsi todistuksella, että neljä väriä riittää. :)
Ratkaisu: Zäki linkitti oikeisiin ratkaisuihin. Ajattelemme karttaa graafina (eli pisteiden ja kaarien verkostona), laittamalla pisteen jokaisen maan keskelle ja laittamalla kaaren kahden rajanaapurin välille. Eli tehtävä on osoittaa, että pisteet (solmukohdat) voidaan värittää 5 värillä, niin että vierekkäiset solmut saavat eri värit.
Miksi kuusi väriä riittää? Väitämme ensin, että on olemassa solmu, jolla on korkeintaan viisi naapuria (eli solmun asteluku on viisi). Tämä seuraa suoraan vihjeestä: jos jokaisella solmulla olisi asteluku 6 tai enemmän, graafissa olisi ainakin 3n kaarta. Mutta tasoon piirrettävässä graafissa on korkeintaan 3n-6 kaarta. Nyt kuusi väriä riittää induktiolla: jos solmuja on alle 7, väite on helppo. Muutoin, poista joku 'asteluku enintään viiden' solmu ja väritä jäljelle jäävä graafi 6 värillä. Selvästikin voimme ongelmitta lisätä poistetun solmun takaisin.
Nyt riittää, että todistamme, ettei kuutta väriä tarvita. Oletetaan, että G on minimi-solmuinen esimerkki tasoon piirrettävästä graafista, joka vaatii kuusi väriä. Voimme olettaa, että G muodostuu vain yhdestä komponentista, sillä muuten voisimme värittää komponentit viidellä värillä erikseen. Teemme saman kuin aiemmin, eli poistamme solmun x, jonka asteluku on korkeintaan viisi ja väritämme loput solmut viidellä värillä.
x:n ympärillä on oltava viisi eriväristä naapuria, muuten voisimme värittää x:n ongelmitta. Olkoon nämä naapurit x_1, x_2, ..., x_5 ja kutsumme värejä 1,2,...,5. Olkoon H(i,j) se graafi, jonka saamme, kun otamme solmuiksi vain ne joiden värit ovat i sekä j (ja näiden väliset kaaret pidetään ennallaan). Jos x_1 ja x_3 olisivat graafin H(1,3) eri komponenteissa, voisimme ongelmitta vaihtaa näiden kahden värin paikkaa yhdessä komponentissa, jolloin x voitaisiin värittää. Siispä x_1 ja x_3 ovat samassa H(1,3) komponentissa. Yhtä lailla x_2 ja x_4 ovat graafin H(2,4) samassa komponentissa. Siispä on polut x_1 – x_3 ja x_2 – x_4, joilla on täysin eri värit. Mutta tämä on mahdotonta, sillä G on tasoon piirrettävä. (Piirrä kuva!) Siispä G:tä ei ole olemassa.
Bonukset: Vihje seuraa Eulerin lauseesta. Neliväriteoreema sen sijaan on kuuluisasti todella vaikeasti todistettavissa.
5 tähteä *****: Järjestät juhlan, missä kellä tahansa toisensa tuntevalla henkilöparilla on tasan yksi yhteinen tuttava. (Voit olettaa, että tunteminen on aina molemminpuolista.) Osoita, että jos kukaan juhlassa ei tunne enemmän vieraita kuin sinä, tunnet itse kaikki vieraat.
Todistus: Zäki linkitti ratkaisuun. Voimme osoittaa, että jos piirrämme graafin, jossa henkilöt ovat solmukohtia ja tuntemiset kaaria, se on seuraavanlainen: sinä olet keskellä, ja kaikki muut muodostavat ympärillesi kolmioita. Mitkä tahansa kaksi kolmiota ovat erillisiä, paitsi että sisältävät sinut. Tästä hypoteesista olisin antanut jo mojovan tähtimäärän.
Itse todistus on vaativampi kuin voisi luulla, (niitä on muutama erilainen) ja siihen tarvitaan aika paljon matikan tuntemusta. Siispä en lähde sitä tässä kertaamaan, mutta graafiteorian määritelmiin tutustuneet voivat lukea kauniin, matriisien ominaisarvoihin perustavan todistuksen vaikkapa sivuilta 17-18 täällä: http://www.cs.elte.hu/~lovasz/eigenvals-x.pdf
*********************************
Uudet pulmat:
1 tähti *: Löydä ja todista numeerinen arvo seuraavalle: 1 2/(1 2/(1 2/(1 2/(1 ...
2 tähteä **: Seitsemän erilaisen positiivisen kokonaisluvun summa on 100. Osoita, että niistä joidenkin kolmen summa on ainakin 50.
3 tähteä ***: Todista, että jos juhlassa on kuusi ihmistä, siellä on oltava kolmikko, jossa joko 'kaikki tuntevat toisensa' tai 'kukaan ei tunne ketään'.
4 tähteä ****: Muodostamme lukujonon 1,0,1,0,1,0,... siten, että seitsemännestä luvusta alkaen otetaan aina kuuden edellisen luvun summan viimeinen numero. Osoita, että jonossa ei milloinkaan esiinny pätkä 0,1,0,1,0,1.
5 tähteä *****: Pyöreän pöydän ympärillä on 2008 tyttöä, joista yksi pitää kädessään n korttia. Jokaisella vuorolla joku vähintään kaksi korttia omaavista tytöistä antaa yhden kortin kullekin vierustoverilleen. Todista, että jos n
Zäki keräsi 10 tähteä ja Hessu 4.5 tähteä. Onnittelut!
Ratkaisut:
1 tähti *: Olkoon shakkilaudan koko n*n, missä n on pariton. Voiko ratsu tehdä seuraavan reissun: Se lähtee jostakin ruudusta liikkeelle, käy kaikissa muissa ruuduissa tasan kerran ja palaa lopussa lähtöruutuun takaisin?
Ratkaisu: Zäki ja Hessu löysivät jujun: Ratsu vaihtaa ruudun väriä joka hypyllä, joten ainoastaan parillinen määrä siirtoja voi johtaa alkuruudun väriin. Siksi kierros on mahdoton.
2 tähteä **: Miehellä on 2 euroa, mutta tarvitsee 10 euroa lempikirjaansa. Hän uhkapelaa rahojaan pelissä, jossa heitetään tasapuolista kolikkoa: kruunan sattuessa panos kaksinkertaistetaan, muuten panos menetetään. Mies pelaa toistuvasti seuraavalla taktiikalla: jos rahaa on alle kuusi euroa, hän laittaa kaiken peliin. Jos rahaa on enemmän, hän pelaa juuri niin paljon, että hänellä on voiton sattuessa tasan 10 euroa. Millä todennäköisyydellä mies onnistuu tavoitteessaan?
Ratkaisu: Hessu löysi ratkaisun. Peruskoululaiselle ja jopa useimmille lukiolaisille tehtävä voisi tuottaa ongelmia, sillä on olemassa mm. ääretön rahaketju 2-->4-->8-->6-->2-->4-->...
Kuvan piirtäminen auttaa. Merkitään p_i = P(voitto tulee jos aloitamme rahasumma i). Selvästikin p_2 = (p_4)/2, p_4 = (p_8)/2, p_8 = (p_6)/2 1/2, p_6 = (p_2)/2 1/2. Sijoittamalla nämä takaisin käänteisessä järjestyksessä, saamme yhtälön p_2 suhteen, josta voi ratkaista p_2 = 1/5.
Ratkaisua voi lyhentää, jos huomaamme, että kuva on symmetrinen niin että p_8 = 1-p_2. Hessu myös mietti, josko tehtävän voisi ratkaista huomaamalla, että peli on reilu (ajatellen sitä kahden hengen pelinä, jossa toisella pelaajalla on aluksi 8 euroa). Mutta peli on reilu joss p_2 = 1/5. Sen me juuri osoitimme! Ei ole mielestäni täysin selvää ensisilmäyksellä, että peli on välttämättä reilu, mutta tämän yksittäisen esimerkin symmetria mahdollistaa sen.
3 tähteä ***: Shakkilaudan koko on n*n. Osa ruuduista on valmiiksi saastuneita. Seuraavassa vaiheessa kaikki ne puhtaat ruudut saastuvat, joilla on vähintään kaksi saastunutta naapuria. Sama jatkuu, kunnes kaikki ruudut ovat saastuneita, tai viruksen leviäminen loppuu. Mikä on minimimäärä alkuperäisiä saastuneita ruutuja, jotta kaikki ruudut saastuisivat lopulta?
Ratkaisu: Hessu huomasi, että n ruutua riittävät, ja että leviäminen pysähtyy kunhan päädymme umpinaisiin suorakulmioihin, jotka ovat vähintään kahden ruudun päässä toisistaan vaaka- tai pystysuunnassa. Tästä hyvästä 1.5 tähteä hänelle. Hän yritti myös perustella, miksi n ruutua tarvitaan, mutta ratkaisuyritys ei täysin vakuuttanut aukottomuudellaan tai selkeydellään.
Tässä hämäävän helppo ratkaisu: Saastuneen alueen yhteenlaskettu ympärysmitta ei koskaan pienene. Kun koko lauta on saastunut, ympärysmitta on 4n. Siispä tarvitsemme ainakin n alkuperäisiä saastuneita ruutuja. Tuo määrä myös riittää: saastuta alussa lävistäjä.
4 tähteä ****: Osoita, että viisi väriä riittää värittämään minkä tahansa paperille piirrettävän kartan, niin että vierekkäisillä alueilla on eri värit.
Vihje: Voit olettaa, että jos tasoon piirrettävässä graafissa on n solmukohtaa ja m kaarta, silloin m on korkeintaan 3n-6.
1 bonustähti: Todista vihje.
10^500 bonustähteä: Osoita, itse keksimälläsi todistuksella, että neljä väriä riittää. :)
Ratkaisu: Zäki linkitti oikeisiin ratkaisuihin. Ajattelemme karttaa graafina (eli pisteiden ja kaarien verkostona), laittamalla pisteen jokaisen maan keskelle ja laittamalla kaaren kahden rajanaapurin välille. Eli tehtävä on osoittaa, että pisteet (solmukohdat) voidaan värittää 5 värillä, niin että vierekkäiset solmut saavat eri värit.
Miksi kuusi väriä riittää? Väitämme ensin, että on olemassa solmu, jolla on korkeintaan viisi naapuria (eli solmun asteluku on viisi). Tämä seuraa suoraan vihjeestä: jos jokaisella solmulla olisi asteluku 6 tai enemmän, graafissa olisi ainakin 3n kaarta. Mutta tasoon piirrettävässä graafissa on korkeintaan 3n-6 kaarta. Nyt kuusi väriä riittää induktiolla: jos solmuja on alle 7, väite on helppo. Muutoin, poista joku 'asteluku enintään viiden' solmu ja väritä jäljelle jäävä graafi 6 värillä. Selvästikin voimme ongelmitta lisätä poistetun solmun takaisin.
Nyt riittää, että todistamme, ettei kuutta väriä tarvita. Oletetaan, että G on minimi-solmuinen esimerkki tasoon piirrettävästä graafista, joka vaatii kuusi väriä. Voimme olettaa, että G muodostuu vain yhdestä komponentista, sillä muuten voisimme värittää komponentit viidellä värillä erikseen. Teemme saman kuin aiemmin, eli poistamme solmun x, jonka asteluku on korkeintaan viisi ja väritämme loput solmut viidellä värillä.
x:n ympärillä on oltava viisi eriväristä naapuria, muuten voisimme värittää x:n ongelmitta. Olkoon nämä naapurit x_1, x_2, ..., x_5 ja kutsumme värejä 1,2,...,5. Olkoon H(i,j) se graafi, jonka saamme, kun otamme solmuiksi vain ne joiden värit ovat i sekä j (ja näiden väliset kaaret pidetään ennallaan). Jos x_1 ja x_3 olisivat graafin H(1,3) eri komponenteissa, voisimme ongelmitta vaihtaa näiden kahden värin paikkaa yhdessä komponentissa, jolloin x voitaisiin värittää. Siispä x_1 ja x_3 ovat samassa H(1,3) komponentissa. Yhtä lailla x_2 ja x_4 ovat graafin H(2,4) samassa komponentissa. Siispä on polut x_1 – x_3 ja x_2 – x_4, joilla on täysin eri värit. Mutta tämä on mahdotonta, sillä G on tasoon piirrettävä. (Piirrä kuva!) Siispä G:tä ei ole olemassa.
Bonukset: Vihje seuraa Eulerin lauseesta. Neliväriteoreema sen sijaan on kuuluisasti todella vaikeasti todistettavissa.
5 tähteä *****: Järjestät juhlan, missä kellä tahansa toisensa tuntevalla henkilöparilla on tasan yksi yhteinen tuttava. (Voit olettaa, että tunteminen on aina molemminpuolista.) Osoita, että jos kukaan juhlassa ei tunne enemmän vieraita kuin sinä, tunnet itse kaikki vieraat.
Todistus: Zäki linkitti ratkaisuun. Voimme osoittaa, että jos piirrämme graafin, jossa henkilöt ovat solmukohtia ja tuntemiset kaaria, se on seuraavanlainen: sinä olet keskellä, ja kaikki muut muodostavat ympärillesi kolmioita. Mitkä tahansa kaksi kolmiota ovat erillisiä, paitsi että sisältävät sinut. Tästä hypoteesista olisin antanut jo mojovan tähtimäärän.
Itse todistus on vaativampi kuin voisi luulla, (niitä on muutama erilainen) ja siihen tarvitaan aika paljon matikan tuntemusta. Siispä en lähde sitä tässä kertaamaan, mutta graafiteorian määritelmiin tutustuneet voivat lukea kauniin, matriisien ominaisarvoihin perustavan todistuksen vaikkapa sivuilta 17-18 täällä: http://www.cs.elte.hu/~lovasz/eigenvals-x.pdf
*********************************
Uudet pulmat:
1 tähti *: Löydä ja todista numeerinen arvo seuraavalle: 1 2/(1 2/(1 2/(1 2/(1 ...
2 tähteä **: Seitsemän erilaisen positiivisen kokonaisluvun summa on 100. Osoita, että niistä joidenkin kolmen summa on ainakin 50.
3 tähteä ***: Todista, että jos juhlassa on kuusi ihmistä, siellä on oltava kolmikko, jossa joko 'kaikki tuntevat toisensa' tai 'kukaan ei tunne ketään'.
4 tähteä ****: Muodostamme lukujonon 1,0,1,0,1,0,... siten, että seitsemännestä luvusta alkaen otetaan aina kuuden edellisen luvun summan viimeinen numero. Osoita, että jonossa ei milloinkaan esiinny pätkä 0,1,0,1,0,1.
5 tähteä *****: Pyöreän pöydän ympärillä on 2008 tyttöä, joista yksi pitää kädessään n korttia. Jokaisella vuorolla joku vähintään kaksi korttia omaavista tytöistä antaa yhden kortin kullekin vierustoverilleen. Todista, että jos n
Vastaukset 5
Vanhimmat
3 tähden ratkaisussa sanoin 'ympärysmitta ei koskaan pienene', vaikka tarkoitin tietysti 'ei koskaan suurene'.
Ennen kuin alan pähkäillä, niin haluaisin
tietää mikä lukujärjestelmä mellä onkaan
kyseessä. Tehtävässähän puhutaan summan
viimeisestä numerosta.
Hessu
... riittää, mutta saat bonuspisteen, jos pohdit asiaa muillekin lukujärjestelmille. ;)
Olisi hyvä mainita onko 1. tehtävässä käytössä
ketjumurtolukujen perustiedot (lukuteorian alkeita).
Kun kyseessä on likimain yksinkertainen jaksollinen päättymätön ketjumurtoluku. Tällöin ratkaisu olisi toisen asteen algebrallinen irrationaaliluku.
Vai tahdotko, että käytetään vielä alkeellisempia menetelmiä?
... käyttää mitä tietoja ja keinoja tahansa.
On hauskaa nähdä miten eri ihmiset, eri tiedoillaan, lähestyvät ongelmia. Mutta koska tehtävä on 1 tähden lämmittely, siitä voi hyvin päätellä, että lukuteoriaa ei välttämättä tarvita. ;)