MU Puzzle - Solution

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:

    “All the followers of science are fully persuaded that the processes of investigation, if only pushed far enough, will give one certain solution to each question to which they can be applied.... This great law is embodied in the conception of truth and reality. The opinion which is fated to be ultimately agreed to by all who investigate is what we mean by the truth, and the object represented in this opinion is the real.”
    —Charles Sanders Peirce (1839–1914)

    “To the questions of the officiously meddling police Falter replied absently and tersely; but, when he finally grew tired of this pestering, he pointed out that, having accidentally solved “the riddle of the universe,” he had yielded to artful exhortation and shared that solution with his inquisitive interlocutor, whereupon the latter had died of astonishment.”
    —Vladimir Nabokov (1899–1977)

    “Let us begin to understand the argument.
    There is a solution to everything: Science.”
    —Allen Tate (1899–1979)