Delta mi!

Od czasów starożytnych Greków wiadomo, że jest pięć brył foremnych: czworościan, sześcian, ośmiościan, dwunastościan i dwudziestościan. W każdym wierzchołku może się spotkać 3, 4 lub 5 trójkątów, 3 czworokąty lub 3 pięciokąty. Dużo później skompletowano wielościany półforemne, jednak i tu w żadnym z nich nie pojawia się siedmiokąt. Spróbujmy dać mu szansę...

Wyobraźmy sobie następującą grę. Mamy planszę o polach ponumerowanych od 0 do 100 i dwa pionki, stojące na początku na polu o numerze 0. Gracze wykonują ruchy na przemian. Gracz rzuca monetą i jeśli wypadnie reszka, to przesuwa swój pionek o 1 pole, a jeśli orzeł – o 5 pól. Wygrywa ten, kto pierwszy dojdzie do pola o numerze 100.

Jak wiadomo, komputery traktują wszystkie dane, na których działają, jako ciągi bitów, z których każdy może mieć dwie wartości (0 lub 1). Przykładowo, ten tekst jest zapisany w ten sposób, że każdej z liter i pozostałych znaków odpowiada ciąg 8 bitów. Daje to czyli 256 możliwości, co w zupełności wystarcza do zapisania wszystkich potrzebnych znaków. Jednak w rzeczywistości różnych znaków występujących w tekście jest mniej. Problem jest więc taki: jak zapisać tekst tak, żeby na każdą jego literę przypadało jak najmniej bitów?