Eka ketju tippui etusivulta, joten tässä uusi.
Säännöt lyhyesti:
1) Tarkoitus on, että olisi yksi avoin pulma kunakin ajanhetkenä, josta keskustellaan. Pulmiin on oltava tunnettu ratkaisu.
2) Kun pulmaan löytyy lopullinen ratkaisu, nopein saa avata uuden pulman. (Käytännössä ratkaisijalla on avausetu.)
3) Uusi pulma tulee avata uudella viestillä, otsikko tyyliin 'Pulma 12: Rikkinäiset Sukat'
4) Jos ratkaisu on väärin, ja uusi pulma on ehditty avata, niitä voidaan ratkaista rinnakkain. (Tämä sillä ehdolla, ettei sääntöä väärinkäytetä tahallaan -- ts. ratkaisun pitää näyttää oikealta, eikä pelkältä pelleilyltä.)
5) Avaaja voi sulkea pulman milloin vain, esittämällä ratkaisun, mutta viimeistään viikon kuluttua avauksesta.
Säännöt lyhyesti:
1) Tarkoitus on, että olisi yksi avoin pulma kunakin ajanhetkenä, josta keskustellaan. Pulmiin on oltava tunnettu ratkaisu.
2) Kun pulmaan löytyy lopullinen ratkaisu, nopein saa avata uuden pulman. (Käytännössä ratkaisijalla on avausetu.)
3) Uusi pulma tulee avata uudella viestillä, otsikko tyyliin 'Pulma 12: Rikkinäiset Sukat'
4) Jos ratkaisu on väärin, ja uusi pulma on ehditty avata, niitä voidaan ratkaista rinnakkain. (Tämä sillä ehdolla, ettei sääntöä väärinkäytetä tahallaan -- ts. ratkaisun pitää näyttää oikealta, eikä pelkältä pelleilyltä.)
5) Avaaja voi sulkea pulman milloin vain, esittämällä ratkaisun, mutta viimeistään viikon kuluttua avauksesta.
Vastaukset 5
Vanhimmat
Pulma 1: Suomessa on useita eri klaaneja ihmisiä. Osoita, että jokaiselle klaanille löytyy erillinen johtaja jos ja vain jos missä tahansa m eri klaanissa on vähintään m ihmistä.
Ihminen voi siis kuulua useampaan klaaniin. Ehdolla tarkoitettiin, että 'minkä tahansa m klaanin jäsenten yhteismäärä olisi vähintään m'.
Epic fail
Kyseessä oli siis versio Hallin marriage teoreemasta.
Ratkaisu. Olkoon klaanijoukot A_1, A_2,...,A_n. Väite on triviaali yhteen suuntaan.
Oletetaan, että jokaisessa m:n A_i:n unionissa on vähintään m jäsentä. Käytämme induktiotodistusta n suhteen.
Oletetaan ensin, että on sellainen l, että joidenkin joukkojen A_1,...,A_l unionissa X on tasan l jäsentä. (Olemme uudelleennumeroineet klaaneja tarvittaessa.) Induktiohypoteesista seuraa, että klaaneille A_1,...,A_l löytyy erilliset johtajat.
Myös joukoille A_(l 1)\X,..., A_n\X (eli poistamme X:n jäsenet), löytyy erilliset johtajat. (Jokaisessa m joukon unionissa listasta A_(l 1),...,A_n on oltava ainakin m jäsentä, sillä niiden näiden m joukon unioni X:n kanssa sisältää ainakin l m jäsentä, oletuksemme takia.)
Nämä johtajat yhdessä riittävät.
Nyt oletetaan, että ei ole sellaista l kuin edellä. Tällöin voimme poistaa yhden A_n jäsenen x, ja miettiä joukkoja A_1\{x},...,A_(n-1)\{x}. Induktiohypoteesi antaa johtajat näille. Yhdessä x:n kanssa nämä johtajat riittävät.
QED
Avatkaa uusi Pulmia!
... tietysti 'on oltava ainakin m jäsentä X:n ulkopuolella'.