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:
“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.
“Who shall forbid a wise skepticism, seeing that there is no practical question on which any thing more than an approximate solution can be had? Is not marriage an open question, when it is alleged, from the beginning of the world, that such as are in the institution wish to get out, and such as are out wish to get in?”
—Ralph Waldo Emerson (1803–1882)