Browse · MathNet
PrintSaudi Arabia booklet 2024
Saudi Arabia 2024 counting and probability
Problem
Let the alphabet has only two letters: and . Is it possible to choose one word of length 5, one word of length 6, ..., one word of length 30 such that any word of length 300 contains one of the chosen words as substring?
Solution
The answer is NO. Consider all words of length 13 and continue them periodically in both directions to create the sequences. For details, take as some original word of length 13 then add to the right and add to the left will result: There are two identical original words as and will generate the unique sequences. For the other words, each of them will generate the same sequences with another 12 words as follows: So in total, the number of distinct sequences is By the definition of the sequences, one can check that any word of length at least 13 may appear only in 1 sequence. Each word of length may appear in at most sequences, since we fix letters and choose another other letters with ways to form a word of length 13 (some of them may coincide). And note that so we will have available sequences.
Final answer
No
Techniques
Enumeration with symmetryPigeonhole principle