Esimerkki: Hattuprobleema

[+]
Kysymyksiä:
  1. Mitä väliä on sillä, että kuljettaja sanoo, että ''ainakin yhdellä matkustajalla on valkoinen hattu'', kaikkihan sen näkevät? Vastaus [+]
    Kaikki tietävät silloin myös, että kaikki tietävät, että kaikki tietävät jne. että ainakin yhdellä matkustajalla on valkoinen hattu.
  2. Miksi juuri kuudennella pysäkillä? Vastaus [+]
    Koska viidennellä, samoin neljännellä pysäkillä jne. kukaan ei astunut ulos.
[+]

Jos alkuperäinen ongelma ei ratkea kannattaa valita tutkittavaksi jokin yksinkertaisempi versio:
Jos linja-autossa on vain yksi henkilö jolla on valkoinen hattu niin hän ei näe yhtään valkoista hattua ja kun kuljettaja sanoo, että ''ainakin yhdellä matkustajalla on valkoinen hattu'', hän ymmärtää, että hänellä on sellainen ja astuu ulos seuraavalla pysäkillä.

[+]

Entä jos kahdella henkilöllä on valkoinen hattu?
Nyt kaikki tietävät että ''ainakin yhdellä matkustajalla on valkoinen hattu'' joten kumpikaan valkohattuisista matkustajista ei pysty suoraan päättelemään, että hänellä on valkoinen hattu eikä astu ulos ensimmäisellä pysäkillä mutta kun kuljettaja on tämän sanonut niin kaikki myös tietävät, että kaikki tietävät, että ''ainakin yhdellä matkustajalla on valkoinen hattu''. Eli ensimmäisen pysäkin jälkeen molemmat matkustajat, joilla on valkoinen hattu voivat päätellä, että toinen valkohattuinen myös näkee valkoisen hatun eli heillä molemmilla täytyy olla valkoinen hattu päässä ja siten astuvat ulos toisella pysäkillä.

[+]

Yleinen tapaus induktiolla:
Olkoon $P(n)$ väite: Jokainen matkustaja päättelee oikein, että hän voi astua ulos $n$:nnellä pysäkillä jos ja vain jos hän näkee $n-1$ valkoista hattua kun tullaan tälle pysäkille.

Jos tämä väite pätee kaikilla $n\geq 1$ niin tästä seuraa, että jos linja-autossa on $m$ matkustajaa joilla on valkoinen hattu, he voivat kaikki astua ulos $m$:nnellä pysäkillä.

  • Edellä näimme, että väite $P(1)$ (ja myös $P(2)$) on tosi.
  • Oletamme, että väite $P(k)$ on tosi. Kun linja-auto on tulossa $k+1$:lle pysäkille niin jokainen matkustaja, joka näkee $k$ valkoista hattua tietää induktio-oletuksen nojalla, että nämä valkohattuiset matkustajat eivät ole nähneet ainoastaan $k-1$ valkoista hattua ennen edellistä pysäkkiä koska silloin he olisivat astuneet ulos ja näin ollen hänellä itsellään täytyy olla valkoinen hattu ja hän astuu ulos $k+1$:llä pysäkillä.
    Induktio-oletuksen nojalla linja-autossa ei voi olla $1,2,\ldots,k$ valkoista hattua linja-autossa kun se on tulossa $k+1$:lle pysäkille koska silloin valkohattuiset olisivat jo astuneet ulos. Mustahattuiset näkevät siis joko vähintään $k+1$ valkoista hattua tai ei yhtään tässä vaiheessa joten jos joku ei näe $k$ valkoista hattua hän ei voi päätellä että hänellä olisi valkoinen hattu ja hänen pitäisi astua ulos linja-autosta.
  • Induktioperiaatteen nojalla toteamme, että $P(n)$ pätee kun $n\geq 1$.