Problem #24
This is a continuation of last week's problem.
There are 2^n "words" of length n using an alphabet consisting of the
letters a and b. For example, the words of length 2 are aa, ab, ba, and
bb. It is easy to find a word of length 5 so that, reading from left to
right, every two letter word appears; reading aabba yields aa, ab, bb,
and ba.
i. Can you find a word of length 2^n + n - 1 so that, reading
from left to right, every word of length n appears?
ii. If our alphabet contains m letters, can you find a word of
length m^n + n - 1 so that, reading from left to right, every word of
length n appears?
SOURCE: Eric Shade