Tietokilpailussa on 12 kysymystä ja kilpailijoita on 100. Jokaiseen kysymykseen ainakin 56% kilpailijoista tietää vastauksen (ts. vähintään 56% tietää vastauksen kysymykseen t, t=1, 2, 3,..., 12).
Osoita, että on olemassa kilpailijakolmikko, joka tietää yhdessä kaikkiin kysymyksiin vastaukset.
- Kysymykset ja se kuinka moni kilpailijoista tietää vastauksen oletetaan siis tunnetuksi jo ennalta ja jokaiselle kysymykselle tietty prosenttiosuus pelaajista tietää oikean vastauksen. Tämän prosenttiosuuden oletetaan siis olevan aina vähintään 56%.
Osoita, että on olemassa kilpailijakolmikko, joka tietää yhdessä kaikkiin kysymyksiin vastaukset.
- Kysymykset ja se kuinka moni kilpailijoista tietää vastauksen oletetaan siis tunnetuksi jo ennalta ja jokaiselle kysymykselle tietty prosenttiosuus pelaajista tietää oikean vastauksen. Tämän prosenttiosuuden oletetaan siis olevan aina vähintään 56%.
Vastaukset 5
Vanhimmat
Kaksi tapaa ratkoa tehtävä.
Olkoot a_i niiden osallistujien lkm, jotka osaavat vastata kysymykseen numero i. Nyt on a_i >=56. Olkoot b_i niiden kysymysten lukumäärä joihin i:nnes osallistuja tietää vastauksen. Nyt on
a_1 ... a_12=b_1 ... b_100.
Voidaan olettaa, että b_i<b_j kun i<j. Nyt
56*12 <= a_1 ... a_12=b_1 ... b_100<=100*b_100. Siis b_100 on vähintään kuusi, eli sadas osallistuja tietää vastauksen ainakin seitsemään kysymykseen.
Toistetaan edellä olevaa viiteen kysymykseen ja 99 osallistujaan, jolloin
a_1 ... a_5=b_1 ... b_99.
Nyt a_1>= 55 koska yksi osallistuja on pois pelistä. Siis 55*5<=99*b_99, eli b_99>2. Siis yksi osallistuja 99 osallistujasta tietää vastauksen ainakin kolmeen kysymykseen jäljelle jääneistä viidestä kysymyksestä.
Tehdään prosessi vielä kerran kahdelle kysymykselle ja 98 osallistujalle. Nyt a_1 a_2=b_1 ... b_98 ja a_i>=54. Siis 54*2<98*b_98 tai b_98>1. Siis jäljellä olevista 98 osallistujasta yksi tietää vastauksen jäljelle jääneisiin kahteen kysymykseen.
Toinen tapa:
Valitaan satunnaisesti kolme osallistujaa sadasta. Koska on vähintään 100-56=44 osalistujaa jotka eivät tiedä vastausta kysymykseen i, todennäköisyys, että kukaan noista kolmesta ei tiedä vastausta kysymykseen i on enintään (56 yli 3)/(100 yli 3). Siten odotusarvo niiden kysymysten lukumäärälle, joita kaikki nuo kolme veijaria ei tiedä, on 12*(44 yli 3)/(100 yli 3)=172/175<1. Siten on olemassa kolme osallistujaa, jotka tietävät vastauksen kaikkiin kolmeen kysymykseen.
Tuo ensimmäinen ratkaisutapa on selkeä. Jälkimmäisessä ensimmäinen lauseke pitäisi olla kai (44 yli 3)/(100 yli 3). Ja ratkaisu perustuu kai idealle, että kun tuo odotusarvo <1, pitää olla suuri joukko kolmen kombinaatioita (jopa yli puolet kaikista), jotka tietävät vastaukset kaikkiin kysymyksiin.
Itsellänikin oli tuo odotusarvotapa mielessä, mutta vähän toisesta suunnasta.
Määritellään todennäköisyysavaruus
S = ({kilpailijakolmikot}, tasajakauma)
ja määritellään satunnaismuuttuja
X = summa_ {k=1}^12 L_k,
missä L_k on indikaattori tapahtumalle A_k = "joku kolmikosta saa kysymyksen k oikein".
Tällöin E[X] = summa_ {k=1}^12 E[L_k] >= 12*(1-44/100*43/100*42/100) > 11,
sillä jokainen E[L_k] = 1*P(A_k) = 1-P(~A_k) >= 1 - 44/100*43/100*42/100.
Koska toisaalta E[X] = summa_{t=1}^12 t*P(X=t), niin täytyy olla P(X=12) > 0 eli olemassa ainakin yksi kolmikko, joka saa yhdessä kaikki kysymykset oikein (muuten E[X] olisi korkeintaan 11.)
Mulla tuli tuossa ajatusvirhe, ei niin, että yli puolet on noita "ei yhtään virhettä" kolmikoita. Siis jos lasketaan kaikkien mahdollisten kolmikoiden vastausvirheiden määrän odotusarvo (0, 1, 2... väärää), merkitsee <1 että joukossa täytyy olla myös tapauksia 0 väärää.
Hyvä tehtävä, onnittelut siitä. Nyt pitää rapsuttaa päätä, kun ei heti juolahda mieleen sopivaa lähestymistapaa.