Solution
The puzzle's solution is no. It is impossible to change the string MI into MU by repeatedly applying the given rules.
In order to prove assertions like this, it is often beneficial to look for an invariant, that is some quantity or property that doesn't change while applying the rules.
In this case, one can look at the total number of I in a string. Only the second and third rules change this number. In particular, rule two will double it while rule three will reduce it by 3. Now, the invariant property is that the number of I is not divisible by 3:
- In the beginning, the number of
Is is 1 which is not divisible by 3. - Doubling a number that is not divisible by 3 does not make it divisible by 3.
- Subtracting 3 from a number that is not divisible by 3 does not make it divisible by 3 either.
Thus, the goal of MU with zero I cannot be achieved because 0 is divisible by 3.
In the language of modular arithmetic, the number of I obeys the congruence
where counts how often the second rule is applied.
Read more about this topic: MU Puzzle
Famous quotes containing the word solution:
“I herewith commission you to carry out all preparations with regard to ... a total solution of the Jewish question in those territories of Europe which are under German influence.... I furthermore charge you to submit to me as soon as possible a draft showing the ... measures already taken for the execution of the intended final solution of the Jewish question.”
—Hermann Goering (1893–1946)
“What is history? Its beginning is that of the centuries of systematic work devoted to the solution of the enigma of death, so that death itself may eventually be overcome. That is why people write symphonies, and why they discover mathematical infinity and electromagnetic waves.”
—Boris Pasternak (1890–1960)
“There’s one solution that ends all life’s problems.”
—Chinese proverb.