"Hattuprobleema, vaihe 4"
Tämä oli tilanne:
- Linja-autossa on 6 matkustajaa joilla on valkoinen hattu
ja 6 joilla on musta hattu ja kaikki hallitsevat indukiopäättelyä.
- Kukaan ei näe omaa hattuaan, mutta kyllä kaikkien muiden.
- Jokaiselle on annettu ohjeeksi, että jos ja kun hän tietää että
hänellä on valkoinen hattu, hänen tulee astua ulos linja-autosta
seuraavalla pysäkillä.
- Kuljettaja sanoo matkustajille, että ainakin yhdellä
matkustajalla on
valkoinen hattu.
- Kuudennella pysäkillä tämän jälkeen kaikki matkustajat, joilla
on valkoinen hattu astuvat ulos linja-autosta.
Induktiopäättely:
- Väite $P(n)$: Linja-autosta astuu ulos matkustajia pysäkillä $n$ jos ja
vain jos linja-autossa on $n$ valkoista hattua.
- $P(1)$ pätee.
- Jos $P(j)$ pätee kun $j\leq k$ ja linja-autossa on $k+1$ valkoista
hattua niin kukaan ei astu ulos pysäkeillä $1,2,\ldots,k$ ja jokainen,
jota näkee vain
$k$ valkoista hattua, eli jokainen jolla on valkoinen hattu, ymmärtää induktio-oletuksen nojalla että silloin
hänelläkin täytyy olla valkoinen hattu ja hän astuu ulos seuraavalla
pysäkillä. Toisin sanoen, $P(k+1)$ pätee.