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.
“Coming out, all the way out, is offered more and more as the political solution to our oppression. The argument goes that, if people could see just how many of us there are, some in very important places, the negative stereotype would vanish overnight. ...It is far more realistic to suppose that, if the tenth of the population that is gay became visible tomorrow, the panic of the majority of people would inspire repressive legislation of a sort that would shock even the pessimists among us.”
—Jane Rule (b. 1931)