Strings in the MIU System

Start by making an observation that will be helpful in excluding impossible results: by repeatedly applying rule 2 to $MI$ , $I$ always comes in powers of 2. Moreover, every $U$ corresponds to 3 $I$ in a previous step and therefore $I$ only disappears in groups of 6. There is an exception when a final U is added to only remove the final three $U$ 's in the string. Though, multiple use of this trick can be replaced with combinations of steps 2,3 and 4 and an eventual sole use of rule 1.

We can now proceed as follows:

$MU$ can't be derived form $MI$ : you could try to repeatedly apply rule 2 to $MI$ , then rule 3 and finally rule 4 so you finally end up with just one $U$ . Though, as noted, rule 1 always gives you a number of $I$ 's that is a power of 2, but you need them to be a multiple of 3 if you want no $I$ 's left.

If you apply the same way of reasoning to $MUIII$ , you see that you'd need to start from $6n+6$ consecutive $I$ 's, so you have 2 $I$ 's followed by $2n+1$ consecutive $U$ that you can eliminate. Again, $6n+6$ is not a power of 2 (It's a multiple of 3!), so it's not a number of $I$ 's that you can have. If rule 1 was applied at some point to eliminate a group of 3 $I$ 's at the end, you'd have to work with $6n+9$ . This number is not only divisible by 3, but it is also an odd number.

Finally, $MIIUIUIIUI$ corresponds to $15+6n$ consecutive $I$ 's, or to $18+6n$ if rule 1 was used. Again, the former number is odd and the latter is a multiple of 3, so none of them is ever a power of 2.

We also give a possible way to obtain the $MIIUIUI$ , i.e. the right answer:

---

P.S. Thanks to everyone ho reported an issue in either the problem or this solution.

Patten matching and replacement are the wolfram language's unique features.

Mathematica Code:

L = Nest[DeleteDuplicates@ Flatten@{#, StringReplaceList[#, {x_ ~~ "I" ~~ WordBoundary :> x ~~ "I" ~~ "U", "M" ~~ x__ ~~ WordBoundary :> "M" ~~ x ~~ x, "III" -> "U", "UU" -> ""}]} &, {"MI"}, 9];

MemberQ[L, #] & /@ {"MU", "MUII", "MIIUIUI", "MIIUIUIIUI"}

Which gives us: {False, True, True, False}

I think the second one and the third one are both correct.

Consider what the rules do to the number of $I$ s in the string.

Rules 1 and 4 do not affect the number of $I$ s. Rule 2 doubles it; rule 3 subtracts 3.

The latter fact suggests that we consider the remainder of $I$ after division by three. Rules 1, 3, and 4 do not affect this remainder. Only rule 2 changes it, according to the pattern $1 \leftrightarrow 2;\ \ \ \ 0 \leftrightarrow 0$ Since we start with one $I$ , the remainder will always be 1 or 2. It is impossible to make it zero; i.e. the number of $I$ s can never a multiple of 3.

Of the four given strings, $MU$ has zero $I$ s; $MUIII$ has three; $MIIUIUIIUI$ has six. These are multiples of 3 and can therefore not be produced. This leaves $\boxed{MIIUIUI}$ with four $I$ s.

---

Recipe for producing a given string:

Let $s = Mx_1x_2\dots x_n$ , with $x_i \in \{ I,U \}$ ; let $a$ be the number of $I$ s, $b$ the number of $U$ s, and $a$ not a multiple of 3. For $j = 1, \dots, b$ , let $c_j$ be the position of the $j$ th $U$ in the string.

$s = MIIUIUI; n = 7, a = 4, b = 2, c_1 = 4, c_2 = 6.$

• Define $m = a + 3b$ . If $a$ is one greater than a multiple of three, let $k$ be the smallest even integer such that $2^k \geq m$ . If $a$ is one less than a multiple of three, let $k$ be the smallest odd integer such that $2^k \geq m$ .

$m = 4 + 3\cdot 2 = 10, k = 4\ \ \ \ (2^4 = 16 \geq 10).$

• Let $s = \tfrac13(2^k - m)$ , which is necessarily an integer. Write $s = 2t + r$ , with $r = 0$ if $s$ is even and $r = 1$ is $s$ is odd.

$s = \tfrac13(2^4 - 10) = 2;\ t = 1, r = 0.$

• Step 1 . Start with $MI$ .

• Step 2 . Apply rule 2 $k$ times.

$MI \mapsto M\underbrace{IIIIIIIIIIIIIIII}_{16\times}$

• Step 3 . Apply rule 3 $b$ times. For $j = 1, \dots, b$ , replace the $III$ starting at position $c_j + 2(j - 1)$ by $U$ .

$MII\underbrace{III}_{4-6}I\underbrace{III}_{8-10}IIIIIII\mapsto MIIUIUIIIIIII$

• Step 4 . If $r = 1$ , apply rule 1.

• Step 5 . Apply rule 3 $s$ times. For $j = 1, \dots, s$ , replace the $III$ starting at position $n + 1 + 3(j - 1)$ by $U$ .

$MIIUIUI\underbrace{III}_{8-10}\underbrace{III}_{11-13}\mapsto MIIUIUIUU$

• Step 6 . Apply rule 4 $t$ times to the last $2t$ characters of the string.

$MIIUIUI\underbrace{UU}_{}\mapsto MIIUIUI$

This recipe generates the string in $k + b + r + s + t$ steps. This may not be optimal; certain strings exhibit symmetry that allows us to apply rule 2 later in the process.

Multiple solutions exist for MIIUIUI, (four are shown, one is elaborated):

Assign I=1 and U=3:

so the transforms (rules) are: R1(x) = x +3, R2(x) = x * 2, R4(x) = x - 6 and R3 has NO CHANGE in value

Interestingly, Rule#2, R2 makes the result EVEN , and is R2 is required for growing a long string (so only if R1 is the last transform, can the answer be odd)

all answers evaluate to: A=3, B=6, C=10 , and D=15, and C is an early candidate being EVEN. In fact, by plain evaluation, NO SOLUTION DIVISIBLE BY 3 IS POSSIBLE as the +3 and -6 and x2 rules can never alter the by-3-divisibility of any number, so only one answer (C = 10) remains. SOLVED!!!

To manually verify this solution, candidate solutions include:

• 10=(1 * 2 + 3) * 2 (not valid solution: ELIMINATED)
• 10= *1 * 2 * 2 * 2 * 2 - 6 * (solution #1: VALID)
• 10= (1 * 2 * 2 * 2 + 3) * 2 - 6 - 6 (solution #2: VALID - see below)
• 10= (1 * 2 * 2 + 3) * 2 * 2 - 6 - 6 - 6 (solution #3: VALID)
• 10= (1 * 2 * 2 * 2 * 2 * 2 + 3) * 2 - ( 6 * 10) (solution #4: VALID)
• ... many other solutions possible

worked example for solution #2:

• R2(MI)=MII (1 * 2 = 2)
• R2(MII)=MIIII (2 * 2 = 4)
• R2(MIIII)=MIIIIIIII (4 * 2 = 8)
• R1(MIIIIIIII) = MIIIIIIIIU (8 + 3 = 11)
• R2(MIIIIIIIIU) = MIIIIIIIIUIIIIIIIIU (11 * 2 = 22)
• R3(MIIIIIIIIUIIIIIIIIU) = MIIUUUIUIUU (22 = 22)
• R4(MII UU UIUI UU ) = MIIUIUI ( 22 - 6 - 6 = 10)

Interesting hint: even interim solutions divisible by three are never allowed, so that hint might help anyone that breaks down the problem into chunks, branches, or is working backwards from the solution.

Taking M=0, I=1, U=0 (mod 3) we obtain that the only rule which changes the sum of letters (mod 3) is rule 2. Since we can only double our sum and start with 0+1=1 the only values we can get are 1 and 2 (mod 3). All answears except for MIIUIUI have a sum equal to 0 (mod 3) thus it is the only possibility.

Each string can be assigned a value $x$ based on its elements by adding $1$ for every $I$ and $3$ for every $U$ . For example, $MI$ will have an $x$ of $1$ and $MIIUIUI$ will have an $x$ of $10$ .

The four rules can then be analyzed in terms of how they affect $x$ : rule 1 increases it by $3$ , rule 2 doubles it, rule 3 doesn't change it, and rule 4 reduces it by $6$ . Now it becomes apparent that $x$ will always have the form $2^m + 3n$ where $m$ and $n$ are integers.

This reduces the problem of determining whether a given string can't be derived (see note) to determining if its $x$ can be expressed in the form $2^m + 3n$ . And because $2^m \bmod 3 \neq 0$ , it follows that $x \bmod 3 \neq 0$ as well.

The $x$ of the 4 options are $3$ , $6$ , $10$ , and $15$ respectively, making option 3 ( $MIIUIUI$ ) the only possible string.

Note: In this solution, I only proved that all acceptable strings have an $x$ of the form $2^m + 3n$ and used modus tollens to disqualify options 1, 2, and 4. This does not imply that all strings with an $x$ of the form $2^m + 3n$ are acceptable; that would be affirming the consequent. The next step would be to try to prove that a string is acceptable if and only if its $x$ is of the form $2^m + 3n$ .

The final result obtained can be said to be derived from M followed by a certain number of I 's ( that is MII or MIIIII and so on). Using rules 1, 2 and 4 the number of I 's can increase by doubling and reduce by 3 each time.

Thus the number of I's is of the form $a \times 2^{b} - 3 \times c$ or $a \times 2^{b}$ , such that a itself is of the aforementioned form or equals 1, the starting value.

This makes it impossible to get the number of I 's to be a multiple of 3. Since 1 is not divisible by 3 , any $a_{0} = 1 \times 2^{b} - 3 \times c$ won't be divisible by 3 and by induction any $a_{N} = a_{N-1} \times 2^{b} - 3 \times c$ will not be divisible by 3 .

Each of the 4 options can be written as

• M III, (3)
• M III III, (6)
• M II III I III I, (10) (hence, this is the only valid option)
• M II III I III II III I, (15)

Let $n$ be the nr of I-equivalents (nr of I's plus 3 times nr of U's) in the string.

If $n=3m$ for some integer $m$ , the solution is impossible. This excludes 3 optional answers.

If $n=3m+1$ , let $k=\frac{4^l -(3m+1)}{3}$ for some large enough $l$ .

If $n=3m+2$ , let $k=\frac{2*4^l -(3m+2)}{3}$ for some large enough $l$ .

1. Start with MI.
2. Double $2l$ times, resp. $2l+1$ times (rule 2).
3. If $k$ is odd, add one U (rule 1).
4. Replace the last $3*k$ I's with U's (rule 3). There are an even nr of U's now at the end.
5. Remove all UU's (rule 4).
6. For every U in the required string, find the corresponding I-triplet and replace that I-triplet with a U (rule 3).

PROOF

Consider the nr. of I-equivalents $n$ and consider the remainder of $n$ after division by 3.

Rule 1 adds $3$ to $n$ . The remainder stays the same.

Rule 2 doubles $n$ . The remainder 0 stays 0; remainder 1 becomes 2 and 2 becomes 1.

Rule 3 doesn't change $n$ . The remainder also stays the same.

Rule 4 reduces $n$ by 6. The remainder stays the same.

If you start with $MI$ , you start with $n=1$ and you can not get a remainder $0$ by using the rules.

If the remainder of the $n$ of the result is $1$ , there is an integer $m$ such that $n=3m+1$ . Let $k=\frac{4^l -(3m+1)}{3}$ for some large enough $l$ . Check that $k$ is always integer since its numerator is always divisible by 3. $k$ now represents the number of I-triplets that we have to remove after doubling to $MII...(2l$ nr of I's $)...I$ to get the string with the correct nr of I-equivalents. We can only reduce two $U$ 's or $6$ I-equivalents per application of rule 4, so we have to add one U first if $k$ is odd. This is always possible because we start with a string ending with I, and doubling keeps an I at the end. Now it's just a matter of replacing the proper I-triplets with a U.

The case where the remainder of the $n$ in the result is 2 is similar.

Three of the answer options have a nr of I-equivalents with remainder 0, so they can't be produced starting with MI.

MIIUIUI can thus be produced. It has $n=10$ with remainder $1$ , $m=3$ , $l=2$ and $k=2$ which is even:

(0) MI

(2) MII

(2) MIIII

(2) MIIIIIIII

(2) MIIIIIIIIIIIIIIII

(3) MIIIIIIIIIIIIIU

(3) MIIIIIIIIIIUU

(4) MIIIIIIIIII

(3) MIIUIIIII

(3) MIIUIUI

$MI \rightarrow MII$ by Rule 2

$MII \rightarrow MIIII$ by Rule 2

$MIIII\ \rightarrow MIIIIIIII$ by Rule 2

$MIIIIIIII \rightarrow MII$ $III$ $I$ $III$ $III$ $III$ $I$ by Rule 2

$MII$ $III$ $I$ $III$ $III$ $III$ $I \rightarrow$ $MIIUI$ $UU$ $UI$ by Rule 3

$MIIUI$ $UU$ $UI$ $\rightarrow$ $MIIUIUI$ by Rule 4

The U is not the problem here since every U can be obtained by consuming three Is. Therefore, we only have to concern about the I. That's to say, we presume that every string in the option can only be obtained by applying rule 2. In addition, as we can hardly manipulate complex strings once there is a U in the string, we can tell every string in the option can only be obtained by doubling I after the M each time. Therefore, we only have to care about the amount of I behind M: if the amount is even, we call it obtainable. How about the U then? As shown in rule 3, a single U can be considered as 3 Is. We can then define S = amount ( I ) + 3 * amount ( U ) where if S is even, this string is obtainable

Given are the four production rules

• $R_1$ (append a U if the string ends with an I)
• $R_2$ (append a copy of the string after the M)
• $R_3$ (replace an III by a U)
• $R_4$ (delete a UU),

a start string $s_0 =$ MI, and four strings, (at least) one of which can be derived from $s_0$ using the rules. The question is: which one? $-$ If a string $t$ results from a string $s$ by using a rule $R$ , let's write $s R \to t$ .

For any $n \in \mathbb{N}$ let's define the set of strings ('words') that can be derived from $s_0$ using $n$ steps by

$W_0 := \{ s_0 \}$

$W_{n+1} := \{ t | \exists s \in W_n$ with $s R_1 \to t \lor s R_2 \to t \lor s R_3 \to t \lor s R_4 \to t \}$

and let $W := \bigcup\limits_{n \in \mathbb{N}} W_n$ denote the set of all derivable strings.

For any string $s$ let $i(s)$ denote the number of "I"s in it. The four rules affect it like this:

• If $s R_1 \to t$ , then $i(t) = i(s)$
• If $s R_2 \to t$ , then $i(t) = 2 \times i(s)$
• If $s R_3 \to t$ , then $i(t) = i(s) - 3$
• If $s R_4 \to t$ , then $i(t) = i(s)$ .

Claim. For all $s \in W$ there are $a, b \in \mathbb{N}$ with $i(s) = 2^a - 3b$ .

Proof. We reformulate the claim as $\forall n \in \mathbb{N}, s \in W_n : \exists a, b \in \mathbb{N} : i(s) = 2^a - 3b,$ and use mathematical induction by $n$ .

$\underline{n = 0}$ . The number of "I"s in $s_0$ , which is 1, can be written as $i(s_0) = 1 = 2^0 - 3 \times 0$ .

$\underline{n \rightarrow n + 1}$ .

Let $t \in W_{n + 1}$ . Then there are $s \in W_n$ and a rule $R$ with $s R \to t$ . By induction hypothesis, there are $a, b \in \mathbb{N}$ with $i(s) = 2^a - 3b$ . There are four cases:

• If $R$ is $R_1$ , then $i(t) = i(s) = 2^a - 3b$ ,
• If $R$ is $R_2$ , then $i(t) = 2 \times i(s) = 2 ( 2^a - 3b ) = 2^{a + 1} - 3 \times (2b)$ ,
• If $R$ is $R_3$ , then $i(t) = i(s) - 3 = 2^a - 3b - 3 = 2^a - 3(b + 1)$ ,
• If $R$ is $R_4$ , then $i(t) = i(s) = 2^a - 3b. \square$

Now for the options:

If $L_1 \in W$ then there are $a, b \in \mathbb{N}$ with $0 = 2^a - 3b$ . Then $2^a = 3b$ . That's not true, because $2^a$ cannot be divided by 3.

If $L_2 \in W$ then there are $a, b \in \mathbb{N}$ with $3 = 2^a - 3b$ . Then $2^a = 3b + 3 = 3(b + 1)$ . Also false for the same reason.

If $L_4 \in W$ then there are $a, b \in \mathbb{N}$ with $6 = 2^a - 3b$ . Then $2^a = 3b + 6 = 3(b + 2)$ . ditto.

We've found: $L_1 \notin W, L_2 \notin W, L_4 \notin W$ .

So a correct answer can only be $L_3$ . Option 3: MIIUIUI .

Applying the rules in reverse to see how each could be arrived at will reveal the answer. MU - MIII Note MU isn't possible from MI since you could get an I by applying rule 2 but if you applied it again you'd get MIIII instead of three I's. Also it takes just a few tries to see that the other rules can do no better than the above MUIII - MIIIIII Now we reversed rule 3 to sub U with three Is and ended up with six Is. Again starting from MI we can apply rule 2 to double I to give MII then applying again we get MIIII and applying again we get MIIIIIIII that is eight Is and not six. From these it's same to say that M(2nI) isn't a possible string if n is odd MIIUIUI - MII(III)I(III)I Note we have a total of eight Is and from what we said above this is entirely possible therefore this is correct For the last option all we need to do to see that it is false is substitute each U with three Is and count the number of Is and check that it is false. There are three Us so those will give 9 Is along with the six remaining Is this gives a total of 15 Is which is odd therefore such a string is not possible.

Calling $s$ a sequence of symbol, $i$ the number of I in it, $u$ the number of U in it, I call

$f(s)=i+3u$

rule 1 is tricky, I'm going to look at a subset of the possible productions generated considering rule 1 only applied at most once and considering it's value removed later by rules 3 and 4. This can could be extended considering the extra cases separately

• t1 times apply rule 2
• t2 times (0 or 1) apply rule 1
• t3 times apply rule 3 (at the end of the sequence, such that (t2+t3) is even)
• (t2+t3)/2 times apply rule 4
• t4 times apply rule 3

With the above constraints:

$f(s)=2^{t1} - 3*t3$

Considering $2^{t1}\not\equiv 0 (\textrm{mod} 3)$ , you can see that f(s) is never a multiple of 3, so f(MI)=3, f(MUIII)=6, f(MIIUIUIIUI)=15 cannot be generated, while f(MIIUIUI)=10 can. you can verify that even relaxing the constrain on the application of rule 1, this holds.

The number of $I$ is never divisible by 3. Indeed, this is true for the starting string $MI$ and this property is stable by the four rules. Hence $MIIUIUI$ is the only possible answer. This does not show that $MIIUIUI$ is derivable though.

To show that this is stable by the four rules, note that rule 1 and rule 4 does not change the number of $I$ . If $n$ is the number of $I$ at a given step and $n$ is not divisible by 3, then by applying rule 2, the number becomes $2n$ which still isn't divisible by 3. By applying rule 3, the number becomes $n-3$ which still isn't divisible by 3.

1. MI <start>
2. MII <rule 2>
3. MIIII <rule 2>
4. MIIIIIIII <rule 2>
5. MIIIIIIIIIIIIIIII <rule 2>
6. MIIUIIIIIIIIIII <rule 3>
7. MIIUIUIIIIIII <rule 3>
8. MIIUIUIUIII <rule 3>
9. MIIUIUIUU <rule 3>
10. MIIUIUI <rule 4> Conclusion: string option C can be derived

Any string of this type can be made only when it satisfy the equation x = 2ⁿ - 3k or we can say x is not divisible by 3. Where x is the number of 'I' in the string and also considering 'U' as 3 'I'. And n is a natural number while k is whole number. For Option 1. MU x = 3. So, 2ⁿ = 3 + 3k So equation can't be satisfy because LHS is not multiple of 3. For Option 2. MUII x = 5. So, by putting n = 3 and k = 1, equation is satisfy. Hence sting could be made by using (Rule 2) 3 times(n = 3) and then (Rule 1),(Rule 3)&(Rule 4) 1- 1 time (k = 1). Similarly for Option 3 method is shown below. For option 4 x = 15 divisible by 3. So can't formed. Please tell me if I wrong. Or this rule is correct. Thanks.