fbpx
0
Pähkinät

Sunnuntaipähkinä 18: Kuutiopyramidi

By 20.3.20167 marraskuun, 2019One Comment

Kuvan pyramidi koostuu 14 kuutiosta. Jokaisen kuution pohjassa on eri nollaa suurempi kokonaisluku. Alimman kerroksen kuutioihin kirjoitettujen kokonaislukujen summa on 50. Ylempien kerrosten kuutioihin kirjoitetut luvut saadaan laskemalla niiden alapuolella oleviin neljään kuutiäon kirjoitettujen lukujen summa. Mikä on suurin mahdollinen kokonaisluku, joka päälimmäisessä kuutiossa voi olla?


Viime sunnuntaipähkinän ratkaisu: Nuorimmalla siskolla on päässään sininen hattu.
Ongelman ratkaisemiseksi aloitetaan luettelemalla kaikki mahdolliset hattujen järjestykset eli permutaatiot. Vasemmanpuolimmaisessa sarakkeessa on vanhin sisko, keskimmäisessä keskimmäinen ja oikeanpuolimmaisessa nuorin sisko. Hattujen permutaatiot ovat
SSSPSSSPSSSPPPSPSPSPP(1)
Vanhin sisko näkee keskimmäisen ja oikeanpuoleisen hatun. Ainoa tapaus, jossa vanhin sisko voisi päätellä hattunsa värin, on alin, jossa kummallakin nuorella siskolla on päässään punainen hattu. Tällöin jäljellä on vain sinisiä hattuja ja vanhin tietäisi hattunsa värin. Tämä vaihtoehto voidaan siis vetää yli.
SSSPSSSPSSSPPPSPSPSPP(2)
Tarkastellaan nyt kahden nuoremman siskon hattujen mahdollisia permutaatioita (ympyröity punaisella).
SSSPSSSPSSSPPPSPSPSPP(3)
Jos keskimmäinen sisko näkisi nuorimmaisen päässä punaisen hatun, hän voisi päätellä, että hänellä itsellään on sininen hattu (SP). Keskimmäinen sisko ei ei tiedä, minkä värinen hattu hänellä on. Tästä nuorimmainen sisko voi päätellä, että hänellä itsellään ei ole punaista hattua. Täten nuorin sisko tietää, että hänen hattunsa on sininen.
Pienenä triviatietona mainttakoon, että hattuongelmien eräs luokka liittyy Hammingin koodeiksi kutsuttuun tiedonsiirrossa käytettyyn virheenkorjausmenetelmään. Niiiden avulla voidaan korjata yhden bitin suuruisia virheitä lähetetystä koodista. Tässä pähkinässä korkeampaa matematiikkaa ei tarvita, mutta joissakin hattuongelmissa paras strategia hyödyntää käytännössä Hammingin koodauksen ideaa.

Artikkelin kuvat: CC-BY-4.0,Terra Cognita.

Juha Pietiläinen

Author Juha Pietiläinen

More posts by Juha Pietiläinen