Vanhaa sekä uutta pulmaa pukkaa jälleen!
Viimekertainen jakso oli varsin haastava: Hessu sai kuitenkin kasaan yhden tähden, ja uusi tuttavuutemme Lassi 4 tähteä. Hyvä tulos ensikertalaiselle... Onnittelut!
Ratkaisut:
1 tähti *: Meillä on kaksi noppaa, mahdollisesti epäreiluja. Voiko noppien jokainen summa olla yhtä todennäköinen?
Ratkaisu: Lassin idea oli aivan oikeilla linjoilla, (alla olevaa perustason ratkaisua mukaillen) -- tosin hän teki pienen ajatusvirheen. Silti yhden tähden arvoinen suoritus.
Olkoon ekan nopan sivutodennäköisyydet p_1,..., p_6 ja tokan q_1,..., q6. Nyt meillä on kaksi eri tapaa todistaa, että haluttu ominaisuus on mahdoton: nätti tapa sekä perustapa niille, jotka eivät tunne todennäköisyysteoriaa.
Nätti tapa: Olkoon P ja Q jakaumia vastaavat todennäköisyysgeneroijafunktiot, eli määritelmän mukaan esim. P=SUM(p_i*x^(i-1)). Tällöin noppasumman generoija on PQ. Huomaa, että voimme olettaa, että P ja Q ovat 5. asteen reaalipolynomeja, sillä jos p_6=0 tai q_6=0, väite on triviaali. Molemmat polynomit omaavat reaalinollakohdan, sillä asteluku on pariton (kompleksinollakohdat tulevat pareittain). Oletetaan, että haluttu ominaisuus olisi mahdollinen: Silloin PQ = (1 x ... x^10)/11, sillä erilaisia summia on 11. Mutta oikea puoli voidaan, geometrisena summana, kirjoittaa muodossa 1/11 * (1-x^11)/(1-x), eli nollakohdat toteuttavat x^11=1 ja x ei ole 1. Joten meillä ei selvästikään ole reaalinollakohtia: kontradiktio.
Perustapa: Oletetaan, että haluttu ominaisuus pitäää ja olkoon r_i = P(summa on i). Nyt r_2 = p_1*q_1 = 1/11 ja r_12 = p_6*q_6 = 1/11, sillä erilaisia summia on 11. Huomaa, että 1/11 = r_7 >= p_1*q_6 p_6*q_1 = p_1/(11p_6) p_6/(11p_1) >= 2/11. Viimeinen epäyhtälö seuraa havainnosta x/y y/x >= 2 (Voit tarkistaa tämän piirtämällä kuvaajan, tai vetoamalla sopivasti logaritmin konkaavisuuteen. Kyseessä on AM-GM-epäyhtälön yksittäistapaus.) Mutta 1/11 < 2/11, joten meillä on kontradiktio.
2 tähteä **: Tytöt menevät joka koulupäivä ruokajonoon eri järjestyksessä. Järjestyksissä on kuitenkin oltava jotain yhtäläisyyttä kaikkiin aiempiin järjestyksiin verrattuna: eli ainakin yhden tytön pitää olla samassa kohdassa. Jos tyttöjä on n, kuinka monta päivää he voivat maksimissaan käydä koulua?
Ratkaisu: Tulkitsemme tehtävän näin: Mikä on maksimimäärä joukon {1,2,...,n} permutaatioita (eli järjestyksiä), niin että mitkä tahansa kaksi permutaatiota osuvat toisiinsa ainakin yhdessä kohdassa? (Toisin sanoen, esim. 123 ja 321 osuvat toisiinsa tokassa kohdassa.) Huomaa, että mikään permutaatio ei osu mihinkään itsensä syklisiin permutaatioihin (eli rullaamme kaiken lopusta alkuun: esim. syklissä 123, 231, 312 mitkään kaksi eivät osu toisiinsa). Voimme valita korkeintaan yhden permutaation jokaisesta syklistä, joten maksimimäärä ei voi ylittää eri syklien määrää, joka on (n-1)! = (n-1)*(n-2)*...*1. Miksi saamme juuri tuon luvun? Jokainen sykli sisältää yhden permutaation, jossa 1 on eka luku. Loppujen n-1 luvun (n-1)! eri järjestystä määrittelevät yksiselitteisesti kaikki eri sykliset tyypit. Voidaanko (n-1)! myöskin saavuttaa? Toki: valitaan jokaisesta syklisestä tyypistä juuri se permutaatio, jossa 1 on ekassa kohdassa. Tällöin kaikki permutaatiot osuvat toisiinsa siinä. Siispä vastaus on (n-1)! .
Hessu ja Lassi antoivat kyseisen ääreistapauksen, ja luottivat sen maksimaalisuuteen, mutta eivät osanneet todistaa asiaa.
3 tähteä ***: Olkoon S numeroituva joukko, ja olkoon A ääretön kokoelma S:n sisäkkäisiä osajoukkoja. Onko A:n oltava numeroituva?
Ratkaisu: Olkoon S = Q, eli rationaalilukujen joukko, joka on selvästikin numeroituva. Olkoon A_r = {q in Q : q
Viimekertainen jakso oli varsin haastava: Hessu sai kuitenkin kasaan yhden tähden, ja uusi tuttavuutemme Lassi 4 tähteä. Hyvä tulos ensikertalaiselle... Onnittelut!
Ratkaisut:
1 tähti *: Meillä on kaksi noppaa, mahdollisesti epäreiluja. Voiko noppien jokainen summa olla yhtä todennäköinen?
Ratkaisu: Lassin idea oli aivan oikeilla linjoilla, (alla olevaa perustason ratkaisua mukaillen) -- tosin hän teki pienen ajatusvirheen. Silti yhden tähden arvoinen suoritus.
Olkoon ekan nopan sivutodennäköisyydet p_1,..., p_6 ja tokan q_1,..., q6. Nyt meillä on kaksi eri tapaa todistaa, että haluttu ominaisuus on mahdoton: nätti tapa sekä perustapa niille, jotka eivät tunne todennäköisyysteoriaa.
Nätti tapa: Olkoon P ja Q jakaumia vastaavat todennäköisyysgeneroijafunktiot, eli määritelmän mukaan esim. P=SUM(p_i*x^(i-1)). Tällöin noppasumman generoija on PQ. Huomaa, että voimme olettaa, että P ja Q ovat 5. asteen reaalipolynomeja, sillä jos p_6=0 tai q_6=0, väite on triviaali. Molemmat polynomit omaavat reaalinollakohdan, sillä asteluku on pariton (kompleksinollakohdat tulevat pareittain). Oletetaan, että haluttu ominaisuus olisi mahdollinen: Silloin PQ = (1 x ... x^10)/11, sillä erilaisia summia on 11. Mutta oikea puoli voidaan, geometrisena summana, kirjoittaa muodossa 1/11 * (1-x^11)/(1-x), eli nollakohdat toteuttavat x^11=1 ja x ei ole 1. Joten meillä ei selvästikään ole reaalinollakohtia: kontradiktio.
Perustapa: Oletetaan, että haluttu ominaisuus pitäää ja olkoon r_i = P(summa on i). Nyt r_2 = p_1*q_1 = 1/11 ja r_12 = p_6*q_6 = 1/11, sillä erilaisia summia on 11. Huomaa, että 1/11 = r_7 >= p_1*q_6 p_6*q_1 = p_1/(11p_6) p_6/(11p_1) >= 2/11. Viimeinen epäyhtälö seuraa havainnosta x/y y/x >= 2 (Voit tarkistaa tämän piirtämällä kuvaajan, tai vetoamalla sopivasti logaritmin konkaavisuuteen. Kyseessä on AM-GM-epäyhtälön yksittäistapaus.) Mutta 1/11 < 2/11, joten meillä on kontradiktio.
2 tähteä **: Tytöt menevät joka koulupäivä ruokajonoon eri järjestyksessä. Järjestyksissä on kuitenkin oltava jotain yhtäläisyyttä kaikkiin aiempiin järjestyksiin verrattuna: eli ainakin yhden tytön pitää olla samassa kohdassa. Jos tyttöjä on n, kuinka monta päivää he voivat maksimissaan käydä koulua?
Ratkaisu: Tulkitsemme tehtävän näin: Mikä on maksimimäärä joukon {1,2,...,n} permutaatioita (eli järjestyksiä), niin että mitkä tahansa kaksi permutaatiota osuvat toisiinsa ainakin yhdessä kohdassa? (Toisin sanoen, esim. 123 ja 321 osuvat toisiinsa tokassa kohdassa.) Huomaa, että mikään permutaatio ei osu mihinkään itsensä syklisiin permutaatioihin (eli rullaamme kaiken lopusta alkuun: esim. syklissä 123, 231, 312 mitkään kaksi eivät osu toisiinsa). Voimme valita korkeintaan yhden permutaation jokaisesta syklistä, joten maksimimäärä ei voi ylittää eri syklien määrää, joka on (n-1)! = (n-1)*(n-2)*...*1. Miksi saamme juuri tuon luvun? Jokainen sykli sisältää yhden permutaation, jossa 1 on eka luku. Loppujen n-1 luvun (n-1)! eri järjestystä määrittelevät yksiselitteisesti kaikki eri sykliset tyypit. Voidaanko (n-1)! myöskin saavuttaa? Toki: valitaan jokaisesta syklisestä tyypistä juuri se permutaatio, jossa 1 on ekassa kohdassa. Tällöin kaikki permutaatiot osuvat toisiinsa siinä. Siispä vastaus on (n-1)! .
Hessu ja Lassi antoivat kyseisen ääreistapauksen, ja luottivat sen maksimaalisuuteen, mutta eivät osanneet todistaa asiaa.
3 tähteä ***: Olkoon S numeroituva joukko, ja olkoon A ääretön kokoelma S:n sisäkkäisiä osajoukkoja. Onko A:n oltava numeroituva?
Ratkaisu: Olkoon S = Q, eli rationaalilukujen joukko, joka on selvästikin numeroituva. Olkoon A_r = {q in Q : q
Vastaukset 15
Vanhimmat
Uuteen kolmen tähden tehtävään oli eksynyt ylimääräinen kysymysmerkki.
Lisäksi neljän tähden tehtävää sopii tarkentaa sen verran, että 'muistavat toisensa' sallii myös tilanteen, jossa ihmiset muistavat sen, että EIVÄT tunne toisiaan. :)
"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?"
Eli miten määritellään, että joku on todennäköistä? Siis onko todennäköistä, jos P > 0,5 vai pitääkö peräti olla, että P > 0,9? Eli minkä on todennäköisyyden oltava tässä tehtävässä, että tapahtuma on todennäköinen vai onko tähän joku olemassa jokin yleinen standarti?
... päätettävissä, mutta eiköhän >0.5 riitä aika pitkälle?
Tietenkin tässä näin voidaan olettaa, mutta tuon "on todennäköistä" kanssa pitää olla tarkkana. Mitäpä tuumaat jos lentäjä sanoo koneessa, että "on todennäköistä, että laskeutuminen onnistuu" tai kirurgi sanoo, että "todennäköisesti leikkauksessa ei ilmene komplikaatioita." Pitäisikö näissä tilanteissa olla jo todella huolestunut, koska todennäköisyyshän voi olla missä tahansa 50% ja 100% välillä, eli vaikkapa 51%, jolloin esim. kirurgin lähes jokatoinen leikkaus epäonnistuu?
Tosiaan tämä on tehtävän kannalta turhaa nipottamista, mutta mietin tätä ongelmaa juuri eilen kun yksi kaveri lupasi koulussa, että "softa todennäköisesti valmistuu huomena." Esitinkin kysymyksen, että "onko softan valmistuminen huomiseksi siis epävarmaa?"
Tuosta ilmeisesti puuttuu sulut: 2^2^n 1=2^(2^n) 1, sillä ASCII-tekstissä on tapana lukea tekstiä oikealta vasemmalle. jolloin 2^2^n=4^n.
... eikö oikealta vasemmalle luettaessa nimenomaan tule 2^(2^n)?
Itse lukisin 2^2^n edellämainitusti, ellei siinä ole (2^2)^n.
Mutta hyvä, että tarkensit.
"... eikö oikealta vasemmalle luettaessa nimenomaan tule 2^(2^n)? "
Oikealta vasemmalle luettaessa tulee, mutta suomea luetaan yleensä vasemmalta oikealle. Jos tämän kirjoittaa matemaattisesti, siis eksponentit yläkulmaan, niin 2^2^n=2^(2^n). Mutta koska ASCII-tekstiin ei saa eksponentteja, tulkitaan potenssit vasemmalta oikealle: 2^2^n=(2^2)^n=4^n.
Eli kirjoitit siis aluksi vahingossa 'oikealta vasemmalle'? ;)
Loppujen lopuksi kuka nyt kirjoittaisi 4^n muodossa 2^2^n, ellei tarvitse? Ajattelin, että ambivalenttisuutta ei käytännössä ole, mutta toki on hyvä pitää kiinni notaatiokäytännöistä.
Millainen äänestystapa on kolmostehtävässä?
Suljettu lippuäänestys? Kuulevatko/näkevätkö
muut toistensa äänestystuloksia?
H
... jos pohtisit näitä eri vaihtoehtoja ja miten tulokset eroavat niissä...
Mutta jos joku kuulee toisen äänestystuloksen tietäen samalla yhteisen sopimussäännön, tällöin hän saattaa epäsuorasti saada tiedon omasta tarrastaan, mikä on kiellettyä.
Suljettu lippuäänestys on varmasti hyvä lähtökohta.
Viikon Pulmat #8 myöhästyy, sillä olen joutunut taistelemaan spämmiä/hyökkäyksiä vastaan tällä foorumilla, enkä ole saanut työrauhaa. Heti kun moderaattori on poistanut yhden riidan, joku aloittaa uuden.
Palaan Viikon Pulmiin sitten kun nämä hyökkäykset ovat päättyneet. Toivottavasti teillä vielä riittää kiinnostusta tuleviin jaksoihin?
Ei kaikkiin kommentteihin tarvitse vastata. Kyllä minäkin saan jatkuvasti spämmiä ja muutama ihminen pitää minua typeränä ihmisenä, mutta en välitä näistä kommenteista. Ihmisillä on eri mielipiteitä asioista ja niin pitää ollakin. Jos kaikki ajattelisivat asioista samalla tavalla, mitään kehitystä ei koskaan tapahtuisi.
... asia erikseen. Niistä ei 'tarvitse' välittää, mutta Minä Välitän. En yksinkertaisesti halua nähdä niitä. Haluan voida keskustella aiheista rauhassa, ilman jatkuvaa panettelua: minulle tulee näiden katselusta päänsärky, eikä niitä voi välttää, kun ne tunkeutuvat joka ketjuun.
Jos itse olen liian kärkevästi keskustellut, viestini on poistettu, ja sillä sipuli. En ole ryhtynyt ketään vainoamaan viikkokaupalla sen jälkeen, perustelemaan ylimääräisiä riitelyketjuja ja keksimään näsäviisauksia. Sen voin sanoa, että jos/kun lähden tältä foorumilta, se ei todellakaan ole minun menetykseni.
Tarkoittiko kysymys todellakin samaa syntymäpäivää vai syntymäpäivien viettoa samana vuoden päivänä? Edellinen tarkoittaa käsittääkseni kaikkia niitä, jotka ovat syntyneet samana vuonna samana päivänä, jälkimmäinen myös niitä, jotka ovat syntyneet eri vuosina, mutta samana päivänä.
Todennäköisesti tulee iso ero noiden kahden vaihtoehdon välille ja jotenkin ensimmäisessä olisi kait otettava väestötiede avuksi?
... ihan vain sitä yksinkertaisempaa vaihtoehtoa, eli sama vuodenpäivä (ei pakosti yhteinen syntymävuosi). En laita tilastollisia kysymyksiä ilman eri mainintaa.
Voitte muuten vielä palautella vastauksia huomiseen klo 18 asti. Yritän silloin laittaa uuden jakson pystyyn.