A language has an alphabet of 3 letters, M, I, and U. Words are formed in this language by the following rules (where “x” and “y” represents any string of letters, not necessarily words).

1: MI is a word

2: if xI is a word, then so is xIU

3: if Mx is a word, then so is Mxx

4: if xIIIy is a word, then so is xUy

5: if xUUy is a word, then so is xy

Question: is MU a word?

(This puzzle is taken from Douglas Hofstadter’s book Gödel, Escher, Bach, where it is used introduce thinking about some of the maths important for computer science).

A language has an alphabet of 3 letters, M, I, and U. Words are formed in this language by the following rules (where “x” and “y” represents any string of letters, not necessarily words).

1: MI is a word

2: if xI is a word, then so is xIU

3: if Mx is a word, then so is Mxx

4: if xIIIy is a word, then so is xUy

5: if xUUy is a word, then so is xy

Question: is MU a word?

(This puzzle is taken from Douglas Hofstadter’s book Gödel, Escher, Bach, where it is used introduce thinking about some of the maths important for computer science).

The prize was won by Mohaned al-Bassam.

You can prove by induction on the number n of applications of any of the rules 2 to 5 to the starting word MI that every work must have a number of I’s not divisible by 3.

Step 1: the claim is true for n=0

MI has one I, and 1 is not divisible by 3.

Step 2: if the claim is true for n=k, then it is true for n=k+1

If the (k+1)’th rule-application is rule 2 or rule 5, it makes no difference to the number of I’s in the word.

If it is rule 3, it doubles the number of I’s. Double any number not divisible by 3, and it is still not divisible by 3.

If it is rule 4, then it reduces the number of I’s by 3. Subtract three from any number not divisible by 3, and it is still not divisible by 3.

So whatever the (k+1)’th rule-application is, the number of I’s is still not divisible by 3.

The claim is true for n=1, and we have proved it is true for n=k+1 if it is true for n=k. Therefore, it is true for all n, by mathematical induction.

But zero is divisible by 3.

Therefore, we cannot have a word with zero I’s in it.

Therefore, MU is not a word.

### Like this:

Like Loading...

*Related*