Viikon Pulmat #4

nkorppi kirjoitti:

Terveiset kaikille! On jälleen aika paljastaa ratkaisut edellisen viikon pulmiin, ja laittaa uutta pähkinää kehiin!

Zäki oli aikamoinen velho, ja keräsi yhteensä 10 tähteä! HX yritti ekaa pulmaa kiitettävästi, mutta se ei mennyt aivan putkeen.

Ratkaisut:

1 tähti * : Kahdelle vangille tarjotaan mahdollisuus tunnustaa rikoksensa. Jos vain yksi tunnustaa, hänet vapautetaan ja toinen hirtetään. Jos molemmat tunnustavat, kumpikin saa 10 vuoden tuomion. Jos kumpikaan ei tunnusta, molemmat selviävät vuoden ehdonalaisella. Yritys kommunikoida toisen kanssa johtaa välittömään hirttotuomioon. Miten vangin kannattaa toimia?

Ratkaisu: Oletetaan, että hirton haitta-arvo on ääretön määrä vuosia, vapauttamisen 0 vuotta ja ehdonalaisen 0.1 vuotta. Huomataan, että riippumatta toisen vangin valinnasta, tunnustaminen on parempi vaihtoehto: Jos kaveri tunnustaa, 10 vuotta on parempi kuin hirtto -- ja jos kaveri ei tunnusta, vapautus on parempi kuin vuosi ehdonalaista. Selvästikin tunnustaminen on parempi vaihtoehto. Molemmat tekevät niin, ja molemmat saavat 10 vuotta vankeutta.

Entä jos molemmat eivät tunnustaisi? Eikö tämä olisi parempi vaihtoehto, sillä molemmat pääsisivät ehdonalaisella? :) Tässä juuri piilee tehtävän juju: oman edun tavoittelu ei pakosti johda parhaaseen lopputulokseen. Mutta koska kommunikointi johti tässä hirttoon, yhteistyö-vaihtoehto jäi käyttämättä.

2 tähteä **: Apina kirjoittaa ikuisesti satunnaisia ASCII-merkkejä paperille. Merkkijono S muodostaa Shakespearin kootut teokset. Olkoon tapahtuma A=(apina kirjoittaa S:n äärettömän monta kertaa). Osoita, että P(A) on joko 0 tai 1.

(Vihje: Jos F_i on kasvava jono sisäkkäisiä tapahtumia, ja F_i --> F, tällöin myös P(F_i) --> P(F).)

2 bonus-tähteä: Osoita, että P(A)=1.

Ratkaisu: Bonuskysymys tietenkin ratkaisee myös peruskysymyksen, mutta annetaan ensin yksinkertainen todistus pääkysymyksestä:

Huomaa, että vihjeen soveltaminen tapahtumien komplementteihin antaa myös symmetrisen tuloksen: Jos F_i on pienenevä joukko sisäkkäisiä tapahtumia, P(F_i) on äärellinen jollekin i:lle, ja F_i-->F, silloin P(F_i)--->P(F).

Muutamia notaatioita:

Olkoon A niin kuin tehtävänannossa,
A_k = {S kirjoitetaan vähintään k kertaa},
A_(k,m) = {S kirjoitetaan vähintään k kertaa m:teen merkkiin mennessä},
ja B_m = {S kirjoitetaan äärettömän monta kertaa merkin m jälkeen}

Riippumattomuudesta seuraa, että

P(A_(k,m) JA B_m) = P(A_(k,m))*P(B_m) = P(A_(k,m))*P(A)

Annetaan k lähestyä ääretöntä, jolloin A_(k,m)-->A_k ja {A_(k,m) JA B_m}---> A.

Vihjeestä seuraa, että

P(A) = P(A_k)*P(A)

Mutta kun k lähestyy ääretöntä, A_k ---> A alaspäin. Siispä vihjeen symmetriasta seuraa, että

P(A) = P(A)*P(A)

Tästä on helppo ratkaista, että P(A)=0 tai 1.

Bonustehtävä: Voimme käyttää esim. Borel-Cantellin kakkoslemmaa tähän. Zäki teki tämän melkein oikein, mutta hänellä oli pientä häikkää tapahtumien riippumattomuuden kanssa. 3 tähteä hänelle.

3 tähteä ***: Kutsutaan 'triadiksi' joukkoa, joka koostuu pisteestä ja kolmesta siitä lähtevästä erillisestä, jatkuvasta kaaresta. Osoita, että reaalitaso ei ole erillisten triadien unioni. (Vihje: Reaalitaso on numeroitumaton.)

Ratkaisu: Zäki huomautti ihan oikein, että Q on tiheä R:ssä. Tämä on tarpeellinen huomio, ja siitä yksi tähti.

Olkoon joukko S sellainen, että se sisältää tietyt ehdot täyttävät ympyrät:

a) Ympyrän keskipiste on rationaalinen, eli Q^2:ssa.
b) Säde on rationaalimittainen.

Jos S:n ympyrästä valitaan kolme erillistä rationaalikaarta (eli kaaria rajaavat kulmat ovat piin rationaali-monikertoja), muodostetaan joukko R kaikkien S:n jäsenten kaikista rationaalisista kaarikolmikoista. Huomaa, että R on numeroituva joukko.

Huomaa, että numeroituva määrä triadeja ei riitä peittämään reaalitasoa, sillä triadilla on nolla-pinta-ala, ja samoin on niiden numeroituvalla unionilla (ks. mitallisuus). Joten triadeja on oltava numeroitumaton määrä.

Oletetaan, että reaalitaso on jaettu onnistuneesti triadeihin. Valitaan jokaiselle triadille sellainen R:n kaarikolmikko, että triadin 3 hiusta osuvat kolmikkoa vastaavaan S:n ympyrään ensimmäistä kertaa juuri noiden erillisten kaarien kohdalla (ja triadin keskipiste on S:n rajaaman kiekon sisällä).

Joku kaarikolmikoista on valittu ainakin kahdelle triadille, sillä muuten triadeja olisi numeroituva määrä. Mutta tämä on selvästikin mahdotonta, sillä nuo kaksi triadia ovat erillisiä (piirrä kuva!).

4 tähteä ****: Osoita, että maapallolla on kaksi vastakkaista pistettä, joilla on täsmälleen sama lämpötila. (Voit olettaa maapallon olevan pallo.)

1 bonus-tähti: Osoita, että maapallolla on kaksi vastakkaista pistettä, joissa on sama lämpötila JA ilmanpaine.

Ratkaisu: Zäki linkitti oikeaan ratkaisuun, mutta se ei ollut aivan oikeassa muodossa. Yhdistäessään sen tähän tehtävään, hän teki pienen virheen. (f(x)-f(-x) pitää tuossa tilanteessa ensin normalisoida.) Siispä tästä tehtävästä hänelle 4 tähteä.

Otetaan mikä tahansa isoympyrä (esim. päiväntasaaja) maapallolla. Voimme olettaa, että lämpötila on jatkuva funktio f tuolta ympyrältä reaalilukuihin. g(x)=f(x)-f(-x) on tällöin myöskin jatkuva funktio ympyrältä reaalilukuihin.

Jos g(x)=0, x ja -x ovat sopivia. Muutoin g(x) ja g(-x) saavat erimerkkisen arvon. Mutta koska g on jatkuva, nolla-arvo on ohitettava jossakin kohtaa ympyrää.

Bonustehtävä: Borsuk-Ulam-teoreema kertoo, että mille tahansa jatkuvalle funktiolle n-ulottuvuuksiselta pallopinnalta joukkoon R^n, on olemassa vastakkaiset pisteet, jotka saavat saman arvon. Todistus tapaukselle n=2 riittäisi maapallolle, ja se onnistuu, jos tietää hieman topologiasta (ks. ilmainen nettikirja Hatcher: Algebraic Topology).

Triviaa: Voidaan myös osoittaa, että mille tahansa maapallon pinnan etäisyydelle d, on olemassa sen etäisyyden toteuttava pistepari, joilla on sama lämpötila JA ilmanpaine!

5 tähteä *****: Olkoon S={1,2,3,...,n}. Olkoon A kokoelma r-kokoisia S:n osajoukkoja. Oletetaan myös, että jos X ja Y kuuluvat A:han, niillä on epätyhjä intersektio. Jos r>n/2, silloin A voi olla kooltaan jopa nCr = #(n-kokoisen joukon kaikki r-kokoiset osajoukot). Osoita, että jos r on korkeintaan n/2, niin silloin |A| on korkeintaan (n-1)C(r-1).

Ratkaisu: Annan tästä Zäkille 2 tähteä oikeasta linkityksestä -- loput tähdet menetettiin, koska hän linkitti aluksi väärään teoreemaan. Eli jos googlaatte tms., olkaa tarkkana! Jos ette muista mikä teoreema on kyseessä, yrittäkää ratkaista se itse alusta...

Mietitään kaikkia n! mahdollisia syklisiä järjestyksiä joukolle S. (Eli ota ympyrä, merkitse aloitus/lopetus-piste y, ja kirjoita luvut 1,...,n myötäpäivään y:stä.)

Oletetaan, että X kuuluu A:han. Väitämme, että se esiintyy kaarena n*r!*(n-r)! eri syklisessä järjestyksessä. Tämän näkee, jos miettii asiaa näin: n mahdollisuutta kaaren alkupisteeksi, r mahdollista järjestystä kaaren sisällä, n-r mahdollista järjestystä kaaren ulkopuolella.

Fiksataan syklinen järjestys. Väitämme, että enintään r kaarta vastaa A:n alkioita. Tämä saadaan intersektio-edellytyksestä seuraavasti: Jos (c_1,...,c_r) on sellainen kaari, joka kuuluu A:han, tällöin korkeintaan yksi kaaripareista (...,c_i) ja (c_(i 1),...) kuuluu A:han, sillä muuten niillä olisi keskenään tyhjä intersektio. Mutta kaikkien A:han kuuluvien kaarien on osuttava kaareen (c_1,...,c_r).

Kun kaikki tähänastinen laitetaan yhteen:
|A|*n*r!*(n-r)! on korkeintaan r*n! . Toisin sanoen |A| on korkeintaan (n-1)C(r-1).

Tämä kuuluisa teoreema tunnetaan nimellä Erdös-Ko-Rado.

*****************************

Uudet Pulmat:

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?

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?

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?

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ää. :)

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.

Lähetä ratkaisut nimimerkin kera osoitteeseen [email protected] ti 22.1. klo 18 mennessä. Voit lisäillä/korjailla vastauksia siihen asti.

kirjoitti:

Anonyymi

Kirjoita kommentti

5000

Lähetä