Zbiór zadań, (zadania różne)
Zadanie 289
Szyfr matematyczny
Każdej literze alfabetu łacińskiego została przyporządkowana liczba porządkowa.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Szyfrowanie wiadomości polega na zastąpieniu każdej litery przypisaną do niej liczbą.
Wiadomość KOBYLA MA MALY BOK po zaszyfrowaniu ma postać ciągu złożonego z cyfr i znaku spacji: 1115225121 131 1311225 21511
O ile szyfrowanie jest jednoznacznie wyznaczone, to odszyfrowanie już niekoniecznie.
Zadanie: ile różnych wiadomości, złożonych ze słów mających sens lub nie, możemy otrzymać w wyniku deszyfracji?
Rozwiązanie
W dowolnym zaszyfrowanym ciągu należy znaleźć wszystkie punkty stałe odwzorowania, czyli takie, dla których dwie kolejne cyfry nie mogą utworzyć litery, lub też cyfry te przypisane są jednoznacznie do konkretnej litery. Istnieje kilka warunków, na które należy zwrócić uwagę:
- każdy znak spacji jest punktem stałym.
- jeśli w ciągu napotkamy zero, to cyfra poprzedzająca ją i cyfra zero jednoznacznie wyznaczają jedną z dwóch liter.
- jeśli bezpośrednio przed cyfrą jest cyfra większa od 2 to te dwie cyfry nie mogą tworzyć litery.
- jeśli bezpośrednio przed cyfrą większą od 6 jest cyfra 2, to także te dwie cyfry nie mogą tworzyć litery.
Każdy taki punkt stały możemy zaznaczyć w ciągu.
W poniższym ciągu punkty te zostały oznaczone znakiem "-".
1115225121 131 1311225 21511
1115-225-121-13-1-13-11225-215-11
Punkty te podzieliły ciąg na pewne podciągi o długościach $k_i$ odpowiednio $4, 3, 3, 2, 1, 2, 5, 3, 2$.
Liczba sposobów odszyfrowania takiego pojedynczego podciągu zależy tylko od jego długości i równa jest $F(k+1)$, gdzie $F(n)$ jest $n$-tą liczbą Fibonacciego.
Łączna liczba różnych wiadomości, które możemy otrzymać w wyniku deszyfracji zaszyfrowanej wiadomości równa jest:
$F(5) \cdot F(4) \cdot F(4) \cdot F(3) \cdot F(2) \cdot F(3) \cdot F(6) \cdot F(4) \cdot F(3) = 5 \cdot 3 \cdot 3 \cdot 2 \cdot 1 \cdot 2 \cdot 8 \cdot 3 \cdot 2 = 8640$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>