MathDB

(564) 5

Part of 1997 Tournament Of Towns

Problems(1)

secret code in which every letter is replaced by a word with max 10 letters

Source: TOT 564 1997 Autumn S A5

9/11/2024
Dima invented a secret code in which every letter is replaced by a word no longer than 1010 letters. A code is called “good” if every encoded word can be decoded in only one way. Serjozha (with the help of a computer) checked that for Dima’s code, every possible word of at most 1000010000 letters can be decoded in only one way. Does it follow that Dima’s code is good? (Note that Dima and Serjozha are Russian, so they use the Cyrillic alphabet, which has 33 33 letters! A word is any sequence of letters.)
(D Piontkovskiy, S Shalunov)
combinatorics