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
I
s 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 cant quite define my aversion to asking questions of strangers. From snatches of family battles which I have heard drifting up from railway stations and street corners, I gather that there are a great many men who share my dislike for it, as well as an equal number of women who ... believe it to be the solution to most of this worlds problems.”
—Robert Benchley (18891945)
“Theres one solution that ends all lifes problems.”
—Chinese proverb.
“The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
—Ludwig Wittgenstein (18891951)