strategy - Can you Turn MI to MU?

Using the letters M, I, and U, which can be used to create words. Can you turn MI into MU using in each step one of the following rules:

• 
  
  

  Insert a U to the end of a word ending in I. e.g: MI becomes MIU.

  
  


• 
  

  Re-insert the letters after the M e.g: MIU to MIUIU.

  
  


• 
  

  Replace the letters III with a U. e.g: MUIIIU to MUUU.

  
  


• 
  

  Get rid of letters UU. For example: MUUU to MU.

  
  
  

Can you use the 4 rules to change the word MI into MU? If so how many does it take?

Note: Please use spoilers.

Answer

This is the MU-Puzzle from one of my favourite books Gödel, Escher, Bach.

The solution is here:

No. It is impossible. The number of Is in the string will never be evenly divisible by 3. You need it to be so that rule 3 can reduce it to 0 and thus acheive the goal. We start with 1 I. We may only double it in the hopes of making it a multiple of 3 - no power of 2 is a multiple of 3 - nor is any number not already a multiple of 3 by any power of 2 divisible by 3. Since we start at 1, it cannot be done.