Maths Olympiad Prep

Library / /7 of 16

, 2024

Combinatorics Difficulty 6.0 AIME, harder Prove it Saudi Arabia

Let the alphabet has only two letters: AA and BB. 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 x1x2x13x_1x_2\dots x_{13} as some original word of length 13 then add x1,x2,x3,x_1, x_2, x_3, \dots to the right and add x13,x12,x11,x_{13}, x_{12}, x_{11}, \dots to the left will result:
x11x12x13(x1x2x13)x1x2x3 \dots x_{11}x_{12}x_{13}(x_1 x_2 \dots x_{13})x_1 x_2 x_3 \dots
There are two identical original words as AAAAAAA\dots A and BBBBBBB\dots B will generate the unique sequences. For the other words, each of them will generate the same sequences with another 12 words as follows:
(x2x3x4x13x1), (x3x4x5x13x1x2), , (x13x1x2x12) (x_2x_3x_4\dots x_{13}x_1),\ (x_3x_4x_5\dots x_{13}x_1x_2),\ \dots,\ (x_{13}x_1x_2\dots x_{12})
So in total, the number of distinct sequences is
213213+2>600. \frac{2^{13}-2}{13}+2>600.
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 n<13n < 13 may appear in at most 213n2^{13-n} sequences, since we fix nn letters and choose another 13n13-n other letters with 213n2^{13-n} ways to form a word of length 13 (some of them may coincide). And note that
(28+27++20)+17=29+16<600 (2^8 + 2^7 + \dots + 2^0) + 17 = 2^9 + 16 < 600
so we will have available sequences.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.