This is an interesting little problem I ran into back when I was in high school: Change the string of letters 'MI' to the string 'MU', using the following rules.

• If a string ends with 'I', 'U' can be added ('MI' 
  can be changed to 'MIU')
• Three 'I's in succession can be changed to a 'U' ('MUIII' can be changed to 'MUU')
• The string 'Mx' (where x is any sequence of letters) can be changed to 'Mxx' ('MUIU' can be changed to 'MUIUUIU')
• Two 'U's in succession can be deleted ('MIUU' can be changed to 'MI')

Solution

The annoying thing about this problem is this: It can't be solved. I had a friend who spent several hours attempting to solve it before bringing it to me; he was not happy to find out the problem was unsolvable. So how do I know it is unsolvable?

Only two of the rules alter the number of I's: the second rule decreases the number of of I's by 3, and the third rule doubles the number of I's. 

If the number of I's is not a multiple of three, neither subtracting 3 or doubling will result in a multiple of three. Since 0 is a multiple of three, we can never get rid of all the I's. 

Isn't that slick?