Noniin, nyt on aika katsoa ratkaisut edellisviikon pulmiin ja julkistaa uudet pähkinät!
Hessu palautti jälleen vastauksia, yhteensä neljän tähden arvoisesti! Hyvä!
Ratkaisut:
1 tähteä * : Otetaan ruudukko, jolla on mittasuhteet 2^n x 2^n, mutta yksi ruutu on poistettu kokonaan. Haluamme laatoittaa sen tiilillä, jotka muodostuvat kolmen ruudun L-kirjaimen muodosta. Osoita, että laatoitus on mahdollinen kaikille n=1,2,3,...
Ratkaisu: Hessu keksi haetun ratkaisun, eli induktiolla! Tapaus n=1 on triviaali. Oletetaan, että laatoitus onnistuu, kun n=k. Nyt mietimme tapausta n=k 1. Jaetaan ruudukko kvadrantteihin (eli neljänneksiin). Voimme hypoteesin avulla laatoittaa sen kvadrantin josta puuttuu yksi ruutu. Loput kvadrantit voidaan nekin laatoittaa, kunhan ensin asetamme yhden L-palan ruudukon keskelle.
2 tähteä ** : Meillä on kymmenen säkkiä kolikoita (jokaisessa ainakin 1000 kolikkoa). Yhdeksässä säkissä kolikot ovat massaltaan 1g, mutta yhden säkin kolikot ovat 2g. Meillä on digitaalivaaka, joka antaa massan gramman tarkkuudella. Selvitä mikä säkki on erilainen tasan yhdellä punnituksella.
Ratkaisu: Hessu keksi tämänkin. Eli järjestä säkit, ja ota 1 kolikko ekasta, 2 kolikkoa tokasta ... jne. Punnituksessa tarkistamme yli 55 menevän grammamäärän. (Sama tehtävä voidaan tietenkin yleistää hieman vaikeamman näköiseksi, esim. niin että tiedämme vähemmän kolikkojen painosta -- mutta ratkaisu on samantyyppinen.)
3 tähteä ***: Osoita, että jos tasoon piirretään mitkä tahansa n pistettä (n>2), eivät kaikki samalla suoralla, niin voimme piirtää suoran joka menee tasan kahden pisteen läpi.
Ratkaisu: Hessulle yksi tähti siitä, että hän huomasi seuraavan lähtökohdan: Tasossa pisteet ja suorat voidaan 'vaihtaa keskenään', niin että etsimmekin sellaista pistettä, jonka leikkaavat tasan kaksi suoraa. (Tämän vastaavuuden voi todistaa projisoimalla tason pallopinnalle, ja määrittämällä pari vastaavuutta sillä.)
Hessun mielestä väite on nyt triviaali -- hän piirsi yhden esimerkin, mutta tämä ei täysin vakuuta minua! Entä jos lisäilemme suoria kaikkiin kahden suoran risteyskohtiin? Miksi synnytämme pakosti uusia kahden suoran risteyksiä? Väite on triviaali, kunhan käytämme seuraavaa lemmaa: tasoon piirrettävä graafi (verkosto) sisältää korkeintaan 3n-6 kaarta, jos siinä on n solmukohtaa. Eli meillä ei voi olla kolme suoraa (eli 6 kaarta) jokaisesta risteyskohdasta!
Tässä hienompi todistus: Oletetaan, että kaikki kaksi pistettä läpäisevät suorat sisältävät yli kaksi pistettä. Valitaan piste P ja (kaksi pistettä läpäisevä) suora L niin, että niiden välinen ei-nolla etäisyys minimoidaan. Piirretään kohtisuora viivasegmentti P:stä L:ään, ja oletetaan, että se leikkaa L:än pisteessä Q. Suoralla L on oltava 3 pistettä, joten kaksi on oltava yhdellä puolelle Q:ta (hyväksymme Q:n sellaiseksi pisteeksi). Olkoon nämä pisteet Q1 ja Q2, niin että Q1 on lähempänä Q:ta. Nyt suoran P-Q2 ja pisteen Q1 välinen etäisyys on pienempi kuin valittu minimietäisyys. Tämä on kontradiktio.
4 tähteä ****: Vankia pidetään ikkunattomassa huoneessa, eikä hän tiedä kellonaikaa. Hänelle kuitenkin kerrotaan, että digitaalikello näyttää aikaa väliltä 12.00 - 23.59 . Hänelle tuodaan pysäytetty, mutta oikeaa aikaa näyttävä viisarikello, jossa minuuttiosoitin on yhtä pitkä kuin tuntiosoitin. Miehen pitää lukea aika oikein, tai hänet hirtetään. Orjuuttaja on nokkela ja on valinnut sellaisen ajan, että vangilla on kaksi yhtä järkevää vastausvaihtoehtoa. Kuinka monta tällaista hetkeä on 12.00 - 23.59 välisenä aikana?
Ratkaisu: Kuvitellaan että meillä on kaksi viisarikelloa, yksi normaali ja yksi nopeammin liikkuva, jonka tuntiviisari liikkuu yhtä nopeasti kuin ensimmäisen minuuttiviisari. Selvästikin haluamme tietää ne ajanhetket, jolloin nämä kaksi kelloa näyttävät samaa aikaa. Poikkeuksena ovat ne ajat, jolloin minuutti- ja tuntiviisari ovat päällekkäin. Siinä ajassa kun normaalin tuntiviisari tekee yhden täyden kierroksen, nopeamman minuuttiviisari tekee 144 kierrosta. Lisäksi normaalin kellon viisarit ovat päällekkäin 12 kertaa. Siispä vastaus on 143-11= 132.
5 tähteä *****: Muodostetaan ruudukko identtisistä tasasivuisista kolmioista. Laattamme ovat muodoltaan kahden vierekkäisen kolmion muodostamia suunnikkaita. Laattoja voi asetella ruudukkoon kolmeen eri asentoon. Osoita, että säännöllisen kuusikulmion (6n^2 kolmiota) onnistuneessa laatoituksessa käytetään yhtä paljon kutakin asentoa.
Ratkaisu: Olkoon eri asennot V (vasen), O (oikea), H (horisontaalinen). On olemassa peruslaatoitus, missä kaikki H:t ovat alimmaisena, V:t vasemmalla ja O:t oikealla. Tässä laatoituksessa on selvästikin samat määrät eri asentoja.
Oletetaan, että laatoituksessa on kolmen eriasentoisen laatan muodostama pikku-kuusikulmio, niin että H on päällimmäisenä. Voimme laittaa H:n tämän pikku-kuusikulmion alimmaiseksi, vaihtamalla näiden 3 laatan keskinäistä sijaintia. Tämä ei muuta eri asentojen määriä laatoituksessa, joten tehdään näitä vaihtoja, niin kauan kuin mahdollista. Väitämme, että näin saavutetaan aiemmin mainittu 'peruslaatoitus'. Tämä riittää todistamaan mitä halusimme.
Jos laatoitus ei ole peruslaatoitus, jonkun H:n alla on oltava H ja joku muu laatta, esim. V ja H -- mutta jälkimmäisen H:n alle on pakko laittaa taas 'V ja H' jne... (Piirrä kuva!) Saamme äärettömän ketjun, mikä on kontradiktio.
************************
Uudet pulmat:
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?
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.
3 tähteä ***: Kutsutaan 'triadiksi' joukkoa, joka koostuu pisteestä ja kolmesta siitä lähtevästä erillisestä viivasegmentistä. Osoita, että reaalitaso ei ole erillisten triadien unioni. (Vihje: Reaalitaso on numeroitumaton.)
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.
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).
Palauta ratkaisut nimimerkin kera osoitteeseen [email protected] maanantaihin 14.1. klo 15 mennessä. Voit korjailla/lisäillä ratkaisujasi siihen saakka!
Hessu palautti jälleen vastauksia, yhteensä neljän tähden arvoisesti! Hyvä!
Ratkaisut:
1 tähteä * : Otetaan ruudukko, jolla on mittasuhteet 2^n x 2^n, mutta yksi ruutu on poistettu kokonaan. Haluamme laatoittaa sen tiilillä, jotka muodostuvat kolmen ruudun L-kirjaimen muodosta. Osoita, että laatoitus on mahdollinen kaikille n=1,2,3,...
Ratkaisu: Hessu keksi haetun ratkaisun, eli induktiolla! Tapaus n=1 on triviaali. Oletetaan, että laatoitus onnistuu, kun n=k. Nyt mietimme tapausta n=k 1. Jaetaan ruudukko kvadrantteihin (eli neljänneksiin). Voimme hypoteesin avulla laatoittaa sen kvadrantin josta puuttuu yksi ruutu. Loput kvadrantit voidaan nekin laatoittaa, kunhan ensin asetamme yhden L-palan ruudukon keskelle.
2 tähteä ** : Meillä on kymmenen säkkiä kolikoita (jokaisessa ainakin 1000 kolikkoa). Yhdeksässä säkissä kolikot ovat massaltaan 1g, mutta yhden säkin kolikot ovat 2g. Meillä on digitaalivaaka, joka antaa massan gramman tarkkuudella. Selvitä mikä säkki on erilainen tasan yhdellä punnituksella.
Ratkaisu: Hessu keksi tämänkin. Eli järjestä säkit, ja ota 1 kolikko ekasta, 2 kolikkoa tokasta ... jne. Punnituksessa tarkistamme yli 55 menevän grammamäärän. (Sama tehtävä voidaan tietenkin yleistää hieman vaikeamman näköiseksi, esim. niin että tiedämme vähemmän kolikkojen painosta -- mutta ratkaisu on samantyyppinen.)
3 tähteä ***: Osoita, että jos tasoon piirretään mitkä tahansa n pistettä (n>2), eivät kaikki samalla suoralla, niin voimme piirtää suoran joka menee tasan kahden pisteen läpi.
Ratkaisu: Hessulle yksi tähti siitä, että hän huomasi seuraavan lähtökohdan: Tasossa pisteet ja suorat voidaan 'vaihtaa keskenään', niin että etsimmekin sellaista pistettä, jonka leikkaavat tasan kaksi suoraa. (Tämän vastaavuuden voi todistaa projisoimalla tason pallopinnalle, ja määrittämällä pari vastaavuutta sillä.)
Hessun mielestä väite on nyt triviaali -- hän piirsi yhden esimerkin, mutta tämä ei täysin vakuuta minua! Entä jos lisäilemme suoria kaikkiin kahden suoran risteyskohtiin? Miksi synnytämme pakosti uusia kahden suoran risteyksiä? Väite on triviaali, kunhan käytämme seuraavaa lemmaa: tasoon piirrettävä graafi (verkosto) sisältää korkeintaan 3n-6 kaarta, jos siinä on n solmukohtaa. Eli meillä ei voi olla kolme suoraa (eli 6 kaarta) jokaisesta risteyskohdasta!
Tässä hienompi todistus: Oletetaan, että kaikki kaksi pistettä läpäisevät suorat sisältävät yli kaksi pistettä. Valitaan piste P ja (kaksi pistettä läpäisevä) suora L niin, että niiden välinen ei-nolla etäisyys minimoidaan. Piirretään kohtisuora viivasegmentti P:stä L:ään, ja oletetaan, että se leikkaa L:än pisteessä Q. Suoralla L on oltava 3 pistettä, joten kaksi on oltava yhdellä puolelle Q:ta (hyväksymme Q:n sellaiseksi pisteeksi). Olkoon nämä pisteet Q1 ja Q2, niin että Q1 on lähempänä Q:ta. Nyt suoran P-Q2 ja pisteen Q1 välinen etäisyys on pienempi kuin valittu minimietäisyys. Tämä on kontradiktio.
4 tähteä ****: Vankia pidetään ikkunattomassa huoneessa, eikä hän tiedä kellonaikaa. Hänelle kuitenkin kerrotaan, että digitaalikello näyttää aikaa väliltä 12.00 - 23.59 . Hänelle tuodaan pysäytetty, mutta oikeaa aikaa näyttävä viisarikello, jossa minuuttiosoitin on yhtä pitkä kuin tuntiosoitin. Miehen pitää lukea aika oikein, tai hänet hirtetään. Orjuuttaja on nokkela ja on valinnut sellaisen ajan, että vangilla on kaksi yhtä järkevää vastausvaihtoehtoa. Kuinka monta tällaista hetkeä on 12.00 - 23.59 välisenä aikana?
Ratkaisu: Kuvitellaan että meillä on kaksi viisarikelloa, yksi normaali ja yksi nopeammin liikkuva, jonka tuntiviisari liikkuu yhtä nopeasti kuin ensimmäisen minuuttiviisari. Selvästikin haluamme tietää ne ajanhetket, jolloin nämä kaksi kelloa näyttävät samaa aikaa. Poikkeuksena ovat ne ajat, jolloin minuutti- ja tuntiviisari ovat päällekkäin. Siinä ajassa kun normaalin tuntiviisari tekee yhden täyden kierroksen, nopeamman minuuttiviisari tekee 144 kierrosta. Lisäksi normaalin kellon viisarit ovat päällekkäin 12 kertaa. Siispä vastaus on 143-11= 132.
5 tähteä *****: Muodostetaan ruudukko identtisistä tasasivuisista kolmioista. Laattamme ovat muodoltaan kahden vierekkäisen kolmion muodostamia suunnikkaita. Laattoja voi asetella ruudukkoon kolmeen eri asentoon. Osoita, että säännöllisen kuusikulmion (6n^2 kolmiota) onnistuneessa laatoituksessa käytetään yhtä paljon kutakin asentoa.
Ratkaisu: Olkoon eri asennot V (vasen), O (oikea), H (horisontaalinen). On olemassa peruslaatoitus, missä kaikki H:t ovat alimmaisena, V:t vasemmalla ja O:t oikealla. Tässä laatoituksessa on selvästikin samat määrät eri asentoja.
Oletetaan, että laatoituksessa on kolmen eriasentoisen laatan muodostama pikku-kuusikulmio, niin että H on päällimmäisenä. Voimme laittaa H:n tämän pikku-kuusikulmion alimmaiseksi, vaihtamalla näiden 3 laatan keskinäistä sijaintia. Tämä ei muuta eri asentojen määriä laatoituksessa, joten tehdään näitä vaihtoja, niin kauan kuin mahdollista. Väitämme, että näin saavutetaan aiemmin mainittu 'peruslaatoitus'. Tämä riittää todistamaan mitä halusimme.
Jos laatoitus ei ole peruslaatoitus, jonkun H:n alla on oltava H ja joku muu laatta, esim. V ja H -- mutta jälkimmäisen H:n alle on pakko laittaa taas 'V ja H' jne... (Piirrä kuva!) Saamme äärettömän ketjun, mikä on kontradiktio.
************************
Uudet pulmat:
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?
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.
3 tähteä ***: Kutsutaan 'triadiksi' joukkoa, joka koostuu pisteestä ja kolmesta siitä lähtevästä erillisestä viivasegmentistä. Osoita, että reaalitaso ei ole erillisten triadien unioni. (Vihje: Reaalitaso on numeroitumaton.)
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.
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).
Palauta ratkaisut nimimerkin kera osoitteeseen [email protected] maanantaihin 14.1. klo 15 mennessä. Voit korjailla/lisäillä ratkaisujasi siihen saakka!
Vastaukset 14
Vanhimmat
Löysätään 3 tähden pulman ehtoa sen verran, että 'viivasegmentit' voivat olla käyriä.
Olenko ihan väsynyt, mutta mielestäni jokainen jana (engl. line segment=jana) on käyrä (helppo nähdä janahomotopian avulla)? Siten käyriä koskeva tulos on yleisempi kuin janoja koskeva, jolloin voimassaoloehdot kiristyvät.
Tarkoitan tietysti: Kiristetään ehtoa. :)
3) Mikä on käyrä? Sivun http://solmu.math.helsinki.fi/1999/5/kivela/ mukaan voidaan asettaa x(t)=a,y(t)=b, jolloin käyrä esittää pistettä (a,b), joka on siten käyrä. Kyllähän reaalitason voi ilmaista tällaisten yksittäisten pisteiden erillisenä yhdisteenä.
Toisaalta jos annetusta pisteestä lähtee kolme eri käyrää, miten käyrät voi olla erillisiä, sillä eikös käyrillä ole yhteinen alkupiste?
... 'any non-trivial Jordan curve'.
... tarkoitettiin, että erillisiä muualla kuin siinä yhdessä pisteessä.
... yleisempi nimitys 'Jordan arc'? No, joka tapauksessa, tarkoitetaan joukkoa, joka on reaalitasossa homeomorfinen joukon {(x,0):x in [0,1]} kanssa.
eddä nvariksensukulainen haluaa osoittaa huikkeaa matematiikan
tietämystään meitien tavallisten lineaarikavereiden joukosa, mutta onko tämä (S24)oekee
foorumj? Onneksi hän jakaa edes bonuspisteitä!!Onkohan han jossain isommissa ympyröissä ehkä onnistunut epä?
Kun me pölkkypäät seikkailemme metrisissä avaruuksissa, kraakkuu hän yleisemmissä topologisissa avaruuksissa.
... minähän vain vastaan, kun kysytään -- tehtävän voi laskea ihan helposti sillä vaikkapa ymmärryksellä, että triadi on piste, josta lähtee kolme ristiämätöntä hiusta. Ihan miten vain haluatte!
... pitäisi epäilemättä pyhittää ala-asteen läksykyselyille... Missä mielessä topologinen avaruus on vaikeampi konsepti kuin metrinen?
Miten arvotetaan keskenään hirttotuomio ja 10 vuoden vankeus. Kumpi on pahempi ja kuinka?
Minusta hirttotuomio on parempi vaihtoehto kuin 10 vuoden vankeus esim,. turkkilaisessa vankilassa tai guantanamossa.
... kunhan selität näkemyksesi!
jos vaikka 85-vuotias saa 10-vuoden tuomion, ei hän välttämättä ehdi kärsimään sitä kokonaan.