Here's a brain teaser...

[mjr]

Some of you may know this one already...

It's called the MU puzzle, and it is as follows:

You have the symbols M, I, and U. You combine them to make words. You start with the word MI and you have to try to convert it to MU, using the following transformation rules:

1. Add a U to the end of any string ending in I. For example: MI to MIU.
2. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
3. Replace any III with a U. For example: MUIIIU to MUUU.
4. Remove any UU. For example: MUUU to MU.

Rules do not have to be followed in order. For instance, you could apply either rule 2 or rule 1 first. Additionally, you cannot use a rule if you cannot apply the rule. The rule must be applied exactly as it is stated.

So, using the parameters above, can you convert MI to MU, in a finite amount of steps? If you can, can you show the steps? Or at least write down the number of rules, in order, to solve the puzzle?

[Jester]

Sure.

You start with MI.

You double the string after M, you get MII.
Since you can double ANY string after M, you double one if the I's, and you get MIII.
(The rules do not state you must double the ENTIRE string after M.)
You replace the III with a U, and you get MU.

Done.

[wolfie]

My understanding is that rule 2 allows duplication of the ENTIRE string (except for the "M"), regardless of what is in that string. Your interpretation of rule 2 makes it a trivial problem, so it's probably not what mjr had in mind.

[dalesys]

... interpretation of rule 2 makes it a trivial problem, so ...

Gordia, meet Lexy. (or knot)

[Jetfire]

Haven't googled it, haven't given it much thought all in all, but my gut feel is that it may not be solvable (short of gordian knot cutting tricks like outlined above). To solve it, you need to be able to get some multiple of 3 I's together so all the I's would cancel out. But you can only increase the I's by power's of 2. ( 1, 2, 4, 8, 16, 32, etc... ) which always alternately leaves 1 or 2 I's left over when you remove all the Trios.

[mjr]

Haven't googled it, haven't given it much thought all in all, but my gut feel is that it may not be solvable (short of gordian knot cutting tricks like outlined above). To solve it, you need to be able to get some multiple of 3 I's together so all the I's would cancel out. But you can only increase the I's by power's of 2. ( 1, 2, 4, 8, 16, 32, etc... ) which always alternately leaves 1 or 2 I's left over when you remove all the Trios.

Keen observation! Correct.

[ArcticChicken]

3. Replace any III with a U. For example: MUIIIU to MUUU.

when you remove all the Trios.

It says any, not all. You don't have to replace all the trios.

Keen observation! Correct.

That you only get doubles, or that it's unsolvable?

[Jetfire]

It says any, not all. You don't have to replace all the trios.

True, you don't need to remove all the triple III's, but removing some of them makes no difference in the end. You'd be left with single and double I's left over that either won't ever form new Triples (making them impossible to remove) or will always have 1 or 2 I's left over even after you remove the triples.

The root of the problem, is that you need some way to turn that single I into some number of III's. But your only tool is to double them, and that will always leave you with I or II left over when you clean out the triples. (That they turn into U's is mostly irrelevant, other than to show you invalid cases).

Any UU's can be dropped immediately because they'd have no bearing on the results. ( MIUU > MIUUIUU > MII; MIUU > MI > MII ; MUUI > MUUIUUI > MII; MUUI > MI > MII )

Any case where you have a U next to an I and not paired with another U, it's an impossible situation, because you'll never get rid of U's to compress the I's together. ( MIU > MIUIU > MIUIUIUIU > etc...)


So you end up with MI > MII > MIIII; from here you can remove a triple and get MIU or MUI, but those will repeat endlessly with no other moves.

You can keep doubling the I's, but that won't get you much either:

MIIIIIIII > MIUUI > MII > (same as above).
MIIIIIIII > MUUII > MII (same as above)
MIIIIIIII > MUIUI > endless UI cycle.

MIIIIIIII > MIIIIIIIIIIIIIIII > MIUUUUIII > MIIII (same as above)
or > MIUUUUU > MIU (endless cycle)

The I's will always have 1 or 2 left over, or they will endlessly cycle.

Thus this is impossible to solve.

[Chromatix]

Fundamentally, this is a lesson about prime numbers and the factors of composite numbers. Notice that there is no addition rule involving the I, only multiplication and remainder-of-division. You can never join two different runs of Is together, because there is no way to delete *all* Us.

You start with a single I. You can multiply it by 2 any number of times, but there will never be a factor of 3 introduced. Therefore, the division by 3 (into Us) will never be exact, *and* the remainder of a division is aways strictly less than the divisor, which is why you always get 1 or 2 remaining.