Problem 114

Problem
of the
Week

PROBLEM 114

You are commissioned to write the dictionary for a new language. The words of this language are all spelled with only the two letters A and Z. A new word is created and entered into the dictionary by applying any one of the four rules below to any word already in the dictionary. (I'll call any consecutive string of letters in a word -- even the empty string of no letters -- a syllable.)

1. From the word x you can create the word xxAAA; for example
ZAZ Þ ZAZZAZAAA.

2. In any word, the syllable AA can be replaced by the syllable Z; for example

AZAAAZ Þ AZZAZ.

3. In any word, the syllable AZA can be deleted; for example,

ZAZAA Þ ZA.

4. In any word, the syllable ZZZ can be replaced by the totality of what follows it; for example,

ZAZZZAAZ Þ ZAAAZAAZ.

You are to begin the dictionary with only a single word spelled "A". Is the word "Z" in your dictionary?

For the much more daring: Given any word in the dictionary, is it possible to transform this word by some sequence of the above operations so as to arrive at a word which is spelled with only the letter A? For example, you can do Z Þ ZZAAA Þ ZZZA Þ AA by applying in turn rules 1, 2, and 4.

Go to the Problem of the Week Home Page