Noniin, pahoittelut myöhästymisestä: tässä uusi jakso Viikon Pulmia viikonloppuviihteeksenne!
Edellisen jakson pulmat osoittautuivat erittäin vaikeiksi: Hessu kuitenkin nappasi kolme tähteä tarrakokoelmiinsa!
Tässä ratkaisut ennen uusia pähkinöitä:
1 tähti * : Kuinka monta ihmistä huoneessa pitää olla, jotta olisi todennäköistä, että kahdella on sama syntymäpäivä? Entä kuinka monta pitää olla huoneessa, jotta olisi todennäköistä, että jollakin on sama syntymäpäivä kuin sinulla?
Ratkaisu: Hessu klaarasi tämän. Tulkitsemme, että 'todennäköinen' tarkoittaa vähintään 1/2 olevaa todennäköisyyttä ja unohdamme myös karkauspäivät. Olkoon n huoneessa olevien määrä ja nPr = n!/(n-r)!
P(kahdella on sama syntymäpäivä) =
1-P(kaikilla on eri syntymäpäivä) =
1 - 365Pn/365^n.
Tämä saa 1/2 ylittävän arvon, kun n>22. Eli 23 henkilöä riittää. (Tämän voi saada kokeilemalla tai käyttämällä Stirlingin approksimaatiota tms.)
Jälkimmäiseen kysymykseen saamme:
P(jollakin on sama syntymäpäivä kuin sinulla) =
1-P(kaikilla on eri syntymäpäivä kuin sinulla) =
1 - (364/365)^(n-1).
Tämä saa 1/2 ylittävän arvon, kun n>253, eli 254 henkilöä riittää.
2 tähteä **: Tutkimalla muotoa 2^2^n 1 olevia lukuja, osoita että alkulukuja on äärettömästi.
Ratkaisu: Hessu löysi tähänkin ratkaisun. Olkoon F_n = 2^(2^n) 1. Idea on todistaa, että luvut F_n ovat keskenään jaottomia, jolloin voimme valita jokaisesta eri alkutekijän. Tällöin alkulukuja on äärettömästi.
Todistamme ensin induktiolla, että
F_1*F_2*...*F_n = F_(n 1)-2.
Oletetaan, että tämä on totta jollekin n, ja mietitään tapausta n 1.
F_1*...*F_n*F_(n 1) = (F_(n 1)-2)*F_(n 1)
= (2^(2^(n 1)) - 1) * (2^(2^(n 1)) 1)
= 2^(2^(n 2))-1
= F_(n 2) - 2.
Oletetaan nyt, että luvuilla F_i ja F_j on yhteinen tekijä d, missä i
Edellisen jakson pulmat osoittautuivat erittäin vaikeiksi: Hessu kuitenkin nappasi kolme tähteä tarrakokoelmiinsa!
Tässä ratkaisut ennen uusia pähkinöitä:
1 tähti * : Kuinka monta ihmistä huoneessa pitää olla, jotta olisi todennäköistä, että kahdella on sama syntymäpäivä? Entä kuinka monta pitää olla huoneessa, jotta olisi todennäköistä, että jollakin on sama syntymäpäivä kuin sinulla?
Ratkaisu: Hessu klaarasi tämän. Tulkitsemme, että 'todennäköinen' tarkoittaa vähintään 1/2 olevaa todennäköisyyttä ja unohdamme myös karkauspäivät. Olkoon n huoneessa olevien määrä ja nPr = n!/(n-r)!
P(kahdella on sama syntymäpäivä) =
1-P(kaikilla on eri syntymäpäivä) =
1 - 365Pn/365^n.
Tämä saa 1/2 ylittävän arvon, kun n>22. Eli 23 henkilöä riittää. (Tämän voi saada kokeilemalla tai käyttämällä Stirlingin approksimaatiota tms.)
Jälkimmäiseen kysymykseen saamme:
P(jollakin on sama syntymäpäivä kuin sinulla) =
1-P(kaikilla on eri syntymäpäivä kuin sinulla) =
1 - (364/365)^(n-1).
Tämä saa 1/2 ylittävän arvon, kun n>253, eli 254 henkilöä riittää.
2 tähteä **: Tutkimalla muotoa 2^2^n 1 olevia lukuja, osoita että alkulukuja on äärettömästi.
Ratkaisu: Hessu löysi tähänkin ratkaisun. Olkoon F_n = 2^(2^n) 1. Idea on todistaa, että luvut F_n ovat keskenään jaottomia, jolloin voimme valita jokaisesta eri alkutekijän. Tällöin alkulukuja on äärettömästi.
Todistamme ensin induktiolla, että
F_1*F_2*...*F_n = F_(n 1)-2.
Oletetaan, että tämä on totta jollekin n, ja mietitään tapausta n 1.
F_1*...*F_n*F_(n 1) = (F_(n 1)-2)*F_(n 1)
= (2^(2^(n 1)) - 1) * (2^(2^(n 1)) 1)
= 2^(2^(n 2))-1
= F_(n 2) - 2.
Oletetaan nyt, että luvuilla F_i ja F_j on yhteinen tekijä d, missä i
Vastaukset 9
Vanhimmat
Ihmettelen tuota vastausta arvaamiskysymykseen (viime viikon tehtävä 3).
Säännöt, jos ymmärsin oikein, ovat nämä:
- jos näet enemmän toista väriä, arvaa sitä
- jos näet yhtä paljon kumpaakin väriä, arvaa mitä vain
Tarkastellaan pari esimerkkiä:
Esimerkki 1, kolme pelaajaa.
Vaihtoehtoja ovat:
kaikilla musta (1 tapaus): kaikki arvaavat oikein.
kaksi mustaa, yksi valkoinen (3 tapausta): 1 pelaajista (valkoinen) näkee 2 mustaa ja vastaa väärin, 2 pelaajista näkee yhden mustan ja valkoisen, ja arvaa 50% todennäköisyydellä oikein.
kaksi valkoista, yksi musta (3 tapausta): kuten kaksi mustaa ja yksi valkoinen yllä, mutta käännetyin värein
kaikilla valkoinen (1 tapaus): kaikki arvaavat oikein.
Meillä on siis 2 tapausta, missä tulos on 3 oikein ja 0 väärin, sekä 6 tapausta, missä tuloksen odotusarvo on 1 oikein. 8 tapauksesta, ennuste siis on 12 oikein 24 arvauksesta, eli 50%.
Esimerkki 2, neljä pelaajaa.
Vaihtoehtoja ovat:
kaikilla musta (1 tapaus): kaikki vastaavat oikein
kolme mustaa, yksi valkoinen (4 tapausta): kolme vastaa oikein, yksi väärin
kaksi mustaa, kaksi valkoista (6 tapausta): kaikki vastaavat väärin (koska näkevät enemmän muita kuin omaa väriään)
yksi musta, kolme valkoista (4 tapausta): kuten kolme mustaa ja yksi valkoinen yllä
neljä valkoista (1 tapaus): kuten neljä mustaa yllä
Meillä on siis 2 tapausta, joiden odotusarvo on 4, 8 joiden odotusarvo on 3, ja 6 joiden odotusarvo on 0. Odotusarvo 16*4=64 'arvaukselle' siis yhteensä 2*4+8*3 = 32, eli 50%.
Vai ymmärsinkö nyt jotain ihan väärin?
Heh, olet oikeassa... Selvästikin oikein veikanneiden määrä on tuolla äänestystaktiikalla keskimäärin aina puolet ihmismäärästä: olet antanut muutamia esimerkkejä, mutta pystytkö todistamaan tämän yleisesti? Yritä, ja jos et osaa, voin auttaa sinua...
Kysymyksen olisi pitänyt olla: Voiko äänestystulos olla oikein suuremmalla todennäköisyydellä kuin 1/2 ?
(Tehtävässä olisi pitänyt myös tarkentaa, että tarrojen värit valitaan satunnaisesti ja toisistaan riippumatta. Oletkin näköjään olettanut sen.)
Olkoon ihmismäärä n.
Ei tarvitse käydä kaikkia eri vaihtoehtoja läpi kunhan miettii asiaa loogisesti:
1) Jos eriväristen tarrojen lukumäärien ero on yli 1, äänestys onnistuu tietysti aina.
2) Jos n on pariton ja eriväristen tarrojen lukumäärien ero on 1, äänestys todennäköisesti epäonnistuu, mutta voi mennä tasan tai onnistua pienemmillä todennäkösyyksillä.
3) Jos n on parillinen ja erivärisiä tarroja on yhtä paljon, epäonnistumme varmasti.
Oletus on, että ihmisiä on huoneessa paljon, jolloin marginaalitapauksella on ohitettavan pieni vaikutus.
Kuinka suuri n riittää, äänestystulos olisi oikein suuremmalla todennäköisyydellä kuin 1/2?
Jos n=2k, riittää, että 2^n > 2*nCk, eli riittää että n>2.
Jos n=2k 1, riittää, että 2^n > 4*nCk, eli riittää että n>7. (mutta pienempikin n saattaa riittää)
Olisiko niin, että tämän voi tulkita eri tavoilla:
"Voiko äänestystulos olla oikein suuremmalla todennäköisyydellä kuin 1/2 ?"
Jos tuolla tarkoitetaan sitä, että äänestystulos on oikein aina jos suurempi osa äänestäjistä veikkaa oikein, ja väärin niissä tapauksissa, että suurempi osa veikkaa väärin, on selvää, että tuo kuvattu äänestystaktiikka toimii. Noin määriteltynä väärä (yli puolet veikkaa väärin) äänestystulos tulee sitä harvemmin, mitä enemmän pelaajia on.
Kuitenkin tuossa tapauksessa missä veikkaus menee väärin (eli alle puolet arvaa oikein), vääriä arvauksia on keskimäärin enemmän kuin oikeita arvauksia niissä tapauksissa, missä äänestys onnistuu (eli yli puolet arvaa oikein). Itse tulkitsin tuon äänestystuloksen todennäköisyyden tarkoittavan yksittäisen äänestäjän mahdollisuutta onnistua, eli että olisi kysytty tätä:
"Onko olemassa taktiikkaa, jolla yksittäisen äänestäjän todennäköisyys arvata värinsä oikein on enemmän kuin 1/2".
Ja tuohon kysymykseen vastaukseni on: ei ole.
Ihan vaan kuriositeettina lisättäköön muuten maininta tilanteesta, missä arvaaminen tapahtuu peräkkäin, siten että kukin kuulee edelliset arvaukset. Tällöin on helppoa löytää taktiikka, jolla 50% todennäköisyydellä yksi arvaa väärin ja muut oikein, ja 50% tn kaikki arvaavat oikein. (Eli itse asiassa vain ensimmäinen arvaa, minkä jälkeen muut tietävät.) Homma toimii vaikka kukaan ei edes näkisi oman lappunsa lisäksi itseään ennen äänestäneiden lappuja, vaan ainoastaan äänestysvuorossa itsensä jälkeisten laput.
... oli tehtävänannossa, ei tulkinnassasi!
Mutta entä jos tehtävä annettaisiin olla virheellisessä muodossaan: Onko taktiikkaa, jolla keskimäärin yli puolet äänestää oikein? Vastasit ei, mutta pystykö todistamaan tämän?
Minulle itselleni riittää todistukseksi seuraava, mutten ole varma, onko se matemaattisessa mielessä riittävä todistus:
Koska jokaisen yksittäisen pelaajan lappu voi olla musta tai valkoinen yhtä suurella todennäköisyydellä täysin muista lapuista riippumatta, ei todennäköisyys arvata se oikein saamatta lapun väristä jotenkin lisätietoa voi myöskään olla mitään muuta kuin 1/2.
Jos joku yrittäisi todistaa asiaa minulle, hyväksyisin itse tuon riittäväksi todistukseksi. Kunhan siis koejärjestely on sellainen, että nuo ehdot (laput toisistaan riippumattomia, pelaaja ei saa lisätietoa) täyttyvät. Jos eivät täyty, tilanne on helposti jotain muuta (esim. kolmen luukun tietokilpailu, jossa juontaja arvauksen jälkeen avaa tyhjän luukun ja kysyy haluatko vaihtaa, mikä on tyyppiesimerkki tilanteesta, missä intuitio saattaa johtaa harhaan).
Vaikkakaan tuo ei saattaisi riittää muodolliseksi todistukseksi, matematiikassa on tärkeää ensin muodostaa jonkinlainen intuitio siitä 'miksi' asian olettaisi olevan tietyllä tavalla... Näin asiasta voi saada vihjeitä ennen kuin sen on todistanut.
Moni lukee valmista todistusta, kaikkine teknisine yksityiskohtineen, eikä tajua matemaatikon ajatteluprosessia kaiken takana: 'Miten tyyppi saattoi keksiä kaiken tämän, ja tälläisessä järjestyksessä?'
Matemaatikko muodostaa hyviä arvauksia erilaisten intuitiivisten yleiskuvien avulla, ja vasta sitten keskittyy yksityiskohtien hiomiseen. Eli hän toimii kuin sarjakuvapiirtäjä, joka piirtää ensin ääriviivat lyijykynällä. Toki yksityiskohdat voivat paljastaa intuition vääräksikin (!), mutta tämä ei heikennä taktiikan arvoa.
Kun on muodostanut intuition asiasta, voi yrittää esittää se muodollisemmin kirjoittamalla se ensin matematiikan kielellä: esim. 'ilman lisätietoa' ilmaistaisiin matematiikassa 'ehdollisen todennäköisyyden' kielellä. Kun tulkitsemme 'ilman lisätietoa' niin, huomaamme, että ehdollisen todennäköisyyden määritelmä itsessään todistaa väitteemme.
On tulkinnanvaraista miten vähän tietoa tehtävä itse asiassa salli, mutta on selvää että ainakin 'enemmistö-taktiikka' ei tuota mitään tietoa: P(lapun väri musta | enemmistö muista lapuista mustia) = 1/2. Jokainen veikkaus on itsessään satunnaisesti oikein, vaikkakin veikkaukset tapahtuvat 'säännön' perusteella. Tapahtumien riippumattomuus päättää todistuksen.
On monta tapaa määritellä ehdollinen odotusarvo, mutta ehkäpä visuaalisin on 'kohtisuora projektio koko tapahtuma-avaruudesta ehto-avaruuteen'. Yhteistä kaikille määritelmille on, että jos ehto-tapahtumat ovat riippumattomia varsinaisista tapahtumista, ne eivät muuta odotusarvoa.
Todellinen kauneus on siinä, että vaikka veikkaukset ovat satunnaisesti oikein, äänestystulos ei todellakaan pakosti ole satunnainen! Tämä on esimerkki siitä, miten 'paikallinen ilmiö' voi olla varsin erilainen kuin 'globaali ilmiö'. Eli filosofisesti tässä on kytkös entropiaan ja kaaosteoriaan.
Onko tehtävässä 5 virhe?
Siinähän sanotaan, että 2k 1, siis pariton,
jakaisi luvun 2^(jotakin).
H
... sillä lukuhan on 2^r - 1, ei suinkaan 2^(r-1). Sulkeita ei ollut.
Toisin sanoen haluamme pienimmän r>0, jolle 2^r = 1 mod 2k 1.
Siinä sanotaan "pienin sellainen r, että 2k 1 jakaa luvun 2^r-1", eli 2k 1 jakaa luvun 2^r vähennettynä yksi, *ei* 2^(r-1). Molemmat käsiteltävät luvut ovat siis parittomia.