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




Back to the Archives

Back to the Math Department Homepage.