Strings in the MIU System

Logic Level 1

In the $MIU$ system, you always start with the string $MI$ and then form new strings by applying any of following rules any number of times:

Rules	Examples
1. If your string ends with $I$ , you can add a $U$ at the end.	$MI\longrightarrow MIU$
2. You can double the entire string following $M.$	$MIU\longrightarrow MIUIU$
3. Three consecutive $I$ 's can be replaced with a single $U.$	$MIIIU\longrightarrow MUU$
4. Two consecutive $U$ 's can be removed from the string.	$MUU\longrightarrow M$

Which of the following strings can be derived from $MI$ using these rules?

Note: None of the rules can be used in the opposite way; for example, you aren't allowed to derive $MUUI$ from $MI$ by using a reversed version of rule 4.

Source: The $MIU$ puzzle was introduced by Douglas Hofstadter in his magisterial work Gödel, Escher, Bach.

Excel in math and science

Master concepts by solving fun, challenging problems.

It's hard to learn from lectures and videos

Learn more effectively through short, interactive explorations.

Used and loved by over 7 million people

Learn from a vibrant community of students and enthusiasts, including olympiad champions, researchers, and professionals.