# OpenLab #4: The MIU puzzle, continued

UPDATE: See the “Assignment Version 2” added below.

This assignment is a continuation of OpenLab #3, on the MIU puzzle.  Your assignment this time is a little different.  Consider the following conjecture about the MIU puzzle:

Conjecture.  Any goal word (any word with first letter M, followed by a combination of U’s and I’s) can be obtained from the starting word MI using the rules of the MIU puzzle.

Assignment (Due Thursday 11/14.  Submit your answer between Tuesday, 11/12 and Thursday, 11/14). Is the conjecture above true?  If so, prove this fact.  If not, provide an example of a goal word that cannot be obtained, and prove that it is impossible for your word to be obtained.

IMPORTANT: Because of the nature of this assignment, DO NOT SUBMIT YOUR ANSWER BEFORE  TUESDAY 11/12. However, I strongly recommend getting started on this problem well before that date!

## ASSIGNMENT VERSION 2

If you wish, you can respond to the assignment below INSTEAD of completing the assignment above.  In the assignment below, you will be writing about your experience working on the MIU puzzle above.  Be sure to respond to EACH PART – detailed answers to part 2 and 3 below will gain the MOST credit.

1. Write down what you think the answer is – no proof necessary.
2. Describe in as much detail as you can the process of working on the assignment.  What did you think in the beginning? What are the different things you tried in order to solve the problem?  Describe each one, in the order that you tried them.
3. Give a detailed list of the resources you used, and how you used each one (these could include anything – your brain, pen & paper, a computer (what applications did you use), the internet, other people, and so on).
4. What activity or resource do you feel was most effective for you in working on the assignment (what helped you the most in understanding the assignment and figuring out an answer)?

Extra Credit.  Respond to one of your classmates’ submissions.

### 26 responses to “OpenLab #4: The MIU puzzle, continued”

1. 1. I believe it is false. I do not believe any word you can possibly think of can be solved using the rules to the MIU puzzle. Will I be able to figure out each and every word? Possibly not, after a while it looks like you are staring at the same thing. I do know though, that I got stuck after a while trying to figure out certain words.

2. This assignment was hard, and very tedious to work on. At the beginning of this I was freaked out by the thought of having to write a proof to go along with the puzzle. Then I figured, it only made sense to bring a proof into it considering everything we have done in this class has lead to this point. It also made sense because most of us thought that playing the MIU puzzle, was similar to doing a proof. The different things I tried in trying to figure out the solution was taking out a sheet of loose-leaf paper and a pencil and
expressing my ideas. I started by thinking of possible words to reach whether easy or hard, and then went through the process of trying to figure it out. At one point the more I’s and U’s I kept writing eventually I started become cross-eyed and had no idea what I was writing. It gets very confusing after a while, especially when you realize all you are looking at are U’s and I’s. (Go figure!)

3. The resources I used were paper, pencil, my notes app on my mac, Microsoft word, brain and I even gave some of my students this same activity to see what they could come up with. (It was worth a try). The way I used my paper and pencil is simply by writing out any and every idea that came to my mind. At the end of it, I had used 5 papers back and front. The way I used my computer is simply by using the same process of pen and paper, but typing it up instead. Rather then continue to go crazy writing down these letters, I got tired and started typing instead. It was somewhat more useful this way because I was able to manipulate letters a lot more easily, and I was able to group things and do whatever it took to lighten the load on my eyes. Eventually, I went back to paper and pencil but the computer was a good alternative for the time being. The way I used my students is simply by pairing them up, teaching them the rules to the game and then letting them find as many different combinations as possible. It was fun to see them apply the rules to this concept, and see their minds in action. After a while I had to ask them to stop because it did not look as if they were going to give up on their own will.

4. What was most useful to me in working on the assignment was simply my eyes, paper and pencil. I could have used the Internet, but I did not want to stumble upon any answers. I wanted to make it as difficult as possible and attempt to do this on my own.

• Great metacognitive reflection – I appreciate the way you touch on both the intellectual and emotional experience! I’d love to know what class you were teaching in which you had students work on this (and seeing some of your students’ work on the puzzle would also be awesome, not sure if it’s possible). Thanks!

• I agree with you, trying to prove the conjecture true was extremely tedious. I thought the previous assignment was difficult trying to prove the puzzles that our classmates posted. It was through trying to prove their puzzle that I came up with my puzzle. How did the student take to you trying out the MIU puzzle on them? Did they give you the O_o look?

2. 1. I think that no, not any word can be obtained by using the MIU puzzle. I couldn’t find a good example, and felt like I was going in circles a bit. But, it seems to be there could be words that do not work.
2. At first I was trying to write out a proof to show that it was true. But I found myself suck (pretty early on!). So, after looking back at my notes, tried different methods, including disproof. I didn’t end up finding an example of disproof either though… I would get confused and felt like I was going in circles.
3. I really mostly used pencil and paper. And my brain I guess! I just find it the easiest way to follow my own steps. I looked up on the Internet, but I really wanted to rely on my own computation, so mostly stuck to pencil and paper.
4. Similar to question 3, I found the most helpful (although I didn’t reach a conclusion) was to keep going through iterations of the puzzle by hand. It helped me think out, single out options, cancel out options, etc. Sometimes when you know the answer it helps you understand how to get there… so hopefully when I see the final answer my scribble and notes will make more sense!

• Patty, I very much agree with you on feeling as if I too was going in circles. It seems like no matter what I did, I ended up back at the same place or feeling as if I was doing the same thing over and over with no end. I also wanted to rely on my own mind and sticking to pencil and paper. It certainly seems like you gave it your best shot. Great effort Patty.

• Great response – your answer to number 4 really resonated for me. Even though it can be frustrating to go through multiple iterations of a process without feeling you are making much progress, that repetition is developing patterns in your mind and thinking that you might not be fully aware of until later. I like to think of this as “laying the ground work for an ah-ha moment”. Your positive attitude reminds me of this page on the Joy of Creative Math Problem Solving: http://www.matholympiad.info/Pages/Attitude.aspx

3. I think we can not obtain every goal word starting with MI using the four rules. and to prove that the conjecture is false I have three examples: 1. MU, 2. MIUIUU, and 3.MUIUU. let’s reach each word;
1. MU
MI to MII (rule 2)
MII to MIII (there is no rule that allows us to add I in this step)
2.MIUIUU
MI to MIU (rule 1)
MIU to MIUIU (rule 2)
MIUIU to MIUIUU (there is no rule to add U to this step)
3.MUIUU
MI to MII (rule 2)
MII to MIIII (rule 2)
MIIII to MUI (rule 3)
MUI to MUIU (rule 1)
MUIU to MUIUU (no rule same thing as the word #2)

• Hi Saloua, I like your approach – you’ve given a few examples, and shown for each of them that the “most natural” approach does NOT work. This kind of work is helpful – it’s a great way to get ideas about the problem. However, it still doesn’t prove that the conjecture is false. For example, it could still be possible that some other approach would work to solve your examples (in fact, I claim that your #2. MIUIUU is, in fact, possible – see if you can figure it out!).

It seems like you’ve done some great work on the problem – I recommend completing the “Version 2” of the assignment, writing about your process, in order to get full credit!

Prof. Reitz

• I had a brainfart in my answer above – I intended to suggest you complete “Version 2” for extra credit (you’ve completed the assignment already!).

4. Albina Yevdayeva

I think that the answer is yes. Someone there should be able to obtain any goal word from the starting word MI , using the rules of the MIU puzzle. I relied on the idea that, for example: the English language comes from Latin, and also it borrows some French and German words , so you can guess that all the words in the language are coming from somewhere; they have the connections. And similarly, all the possible words in the puzzle, should come from somewhere else.
This assignment was, actually, tough. It was not as the previous ones, where you could spend several hour, but still get the answer at the end.
From the beginning, I was just thinking about the problem. I wanted to find the idea, if the answer is yes, or no. Then I tried to work with paper and pencil. I don’t remember how many papers did I use, but the fact is, that I couldn’t prove it. After that, I went to the tutoring center, on the AG floor, and guess what? they could not solve it too. But they said that they liked it, working on the problem, helped them to wake up. I didn’t give up, and went to the tutoring center, on the 6 floor, where the tutors, are mostly the students, and according that I don’t have the answer, they couldn’t help me either. So today, I decided to check up “the ocean of information” on the Internet. I found the explanation of the actual puzzle, but there was no prove. And now, I gave up.
I did not get to conclusion, so I can’t tell you what was helpful for me. Nothing was helpful enough to help to find the answer. But I would say that searching through the Internet, did not help me too, but I found some different information about the puzzle and the author, which is not bad at all to know.
And I hope that in class we will go over it and you tell us the right answer 🙂

• Hi Albina,
I really like the way you took insight from one area (development of languages) and transferred it to another area (working with words in the puzzle) – this kind of crossing of subject boundaries can be a great source of inspiration, and a driver of intuition. Of course, analogy is never perfect, and as you discovered, intuition led you to a wrong conclusion in this case. Welcome to the the life of a mathematician! Nice work.
-Prof. Reitz

5. Albina Yevdayeva

Ricky, when I read your writing that you did not want to use the Internet, in order to make it even harder, “as difficult as possible”, as you said, I wanted to applause you. Making yourself strong and not ran to the computer to check every single idea that comes to mind, it is so unbelievable nowadays. Good for you! But maybe I am stereotyping?

6. I believe that the conjecture is false. Interestingly enough, my proof comes from attempting to solve some of the puzzles people put up in the first MIU puzzle.

Observe the following goal word: MUIUIIUU
Let’s assume that this goal word was obtained from the initial word “MI”. It follows that you should be able to work backwards and eventually obtain MI from MUIUIIUU. So in order to obtain MI, I’ll be using the following rules.

1. Remove a U from the end of any string ending in IU. For example: MIU to MI, or MUUIIU to MUUII.
2. Remove any doubles in any string after the M (that is, change Mxx, to Mx, where ‘x’ represents any string of symbols). For example: MIUIU to MIU.
3. Replace any U with a III. For example: MUUU to MUIIIU.
4. Add any UU. For example: MU to MUUU (probably the trickiest of the rules to use).

These rules can be used to obtain MI as long as the goal word can be obtained from MI in the puzzle. For example:

MUIU

1. MUIU -> MUI (Rule 1)
2. MUI -> MIIII (Rule 3)
3. MIIII -> MII (Rule 2)
4. MII -> MI (Rule 2)

You can use rule 4 to add any number of ‘UU’ strings and still obtain the original word. MUIU -> MUIUUUUU -> MIx16U – MIx16 -> MIx8 -> MIIII -> MII -> MI.

First attempt

1. MUIUIIUU ->MUIUII(III)U (Rule 3)
2. MUIUII(III)U -> MUIUIIIII (Rule 1)
3. MUIUIIIII -> M(III)I(III)IIIII (Rule 3)
4. M(III)I(III)IIIII -> Nothing.

At this point, there’s nothing you can do. There are an odd number of ‘I’s, so you can’t use rule 2 to remove doubles. There are no more ‘U’s to remove after the end of the string, since you removed the only U in the string in step 1. There are no Us left to replace. And using rule 4 to add ‘UU’ anywhere into the string achieves nothing. If you were to treat U as III in this case, you’d be adding 6 ‘I’s to 15 ‘I’s, which would still give you an odd number. So let’s try this again.

Second attempt

1. MUIUIIUU -> M(III)I(III)II(III)U (Rule 3)
2. M(III)I(III)II(III)U -> M(III)I(III)II(III) (Rule 1)
3. M(III)I(III)II(III) -> MIIIIII (Rule 2)
4. MIIIIII -> MIII (rule 2)

And now we’re stuck again. Even with an even number of Is, we couldn’t end up with MI. 12 is a multiple of 3, so removing half of that gets 6, and removing half of that gets 3, which you can’t do anything with. The same problem occurs with any even number that happens to be a multiple of 3.

Third attempt

1. MUIUIIUU -> MUUUIUUUIIUU (Rule 4)

At this point, we can already stop because we’ve already run into the same problem we did in the first attempt. We cannot create any string doubles because it isn’t possible to get rid of the ‘IUU’ at the end of the current string using any of the rules.

Looking at the solutions people were putting up to the other puzzles, I noticed a trend. Every word could be obtained by doubling the string at some point. Aside from the goal word MIU, it is necessary to double the number of Is in order to obtain any other outcome. So unless you add a U onto the end of a string of Is, you’ll always end up with an even number of Is that isn’t a multiple of 3 (mainly because you can’t obtain any multiples of 3 from 2^n). And if you end up with an odd number of Is, you’ll be able to remove a U (which counts as 3 Is) and go backwards in order to get where you want.

But no matter what we do with this word, it simply isn’t possible here. This goal word cannot be obtained at all because it requires you to somehow end up with an odd number of Is in order to do so. The same applies for any goal word that does this. To clarify, it is not possible to obtain any goal word in the MIU puzzle if and only if the goal word has an odd number of ‘I’s > 1. And to prove this, use a much simpler word. Try using the MIU puzzle to solve MIIIU. Or MUIUII. You won’t be able to do it.

Credit goes to Saloua here, mainly because I spent over two hours trying to solve her word last week. I thank you for making that puzzle impossible, because it served to make this homework assignment easier for me. 😛

• I like your reasoning, though I think there are some problems with it here and there. Specifically:

1. In the way that you choose to show that the chosen strings are impossible, you make the statement ” It follows that you should be able to work backwards and eventually obtain MI from MUIUIIUU.” That statement is very powerful, but unproven. It seems like its common sense, but that doesn’t imply that its true. They’re frustrating, I have an unproven statement in my own proof. I just can’t think of a good way to prove it yet.

2. In putting up these sort of inverse solutions, you’re showing, for the most part, that the inverse solutions that you used don’t lead to the goal words, rather than that there exist no inverse solutions to a goal word.

3. You stated that for all strings such that the amount if I’s in the string is odd and greater than 1 have no solutions. There are counterexamples to this:

I’ll borrow your notation for repeated characters:

Goal Word: MIx5

MI – MII (Rule 2)
MII – MIx4 (Rule 2)
MIx4 – MIx8 (Rule 2)
MIx8 – MIx8U (Rule 1)
MIx8 – MIx5UU (Rule 3)
MIx5UU – MIx5 (Rule 4)

This resultant string has an odd amount of I’s which is greater than 1.

There are many things that I agree with. I agree that the amount of I’s in a string can never be a multiple of 3. I also agree that the use of Rule 2 is a part of obtaining the solutions to many words. I use it as a big part of my proof.

Finally, you have the most important part of proving that any string with an amount of I’s that is a multiple of 3 has no solution. You noticed that for any natural number $n in \mathbb{N}$, $3 \not| \; 2^n$. That’s mainly the reason why this is true.

• To fix up that latex error in the second to last sentence, it was:

$n \in \mathbb{N}$, $3 \not| \; 2^n$.

• Darnell – What a great process! I really think your insight to “work backwards” is a significant one – very good thinking. Your list of “reverse” rules is an excellent tool for doing this analysis. The various attempts you show demonstrate that, for a number of the “most natural options”, we can’t reverse engineer our way back to the start MI. This is very suggestive! Though still not a complete proof – since it’s possible that there might be some other attempt that worked…

It seems like you’ve done some great work on the problem – I recommend completing the “Version 2″ of the assignment, writing about your process, in order to get full credit!

Prof. Reitz

• I had a brainfart in my answer above – I intended to suggest you complete “Version 2” for extra credit (you’ve completed the assignment already!).

7. I knew that this was false because I did a little research on the Miu puzzle when the assignment was first given . I did come across the famous example of it being false.
2)Since I knew that there was a case of it being false I tried to come up with my own goal word that would also prove the conjecture false but I had no luck . I think after two hours of trying I gave up and decide I was not going to do the assignment until I saw the second part to the assignment that was later added.
3) The resources I use for this assignment were my brain, pencil ( I did a lot of erasing) ,papers,the internet and the lists of rules on a piece of paper
4) What I found most useful was me just being in solitude and working on this assignment because I realized when I was lets say the library or in a noisy place I couldn’t focus as much and had to start over way more frequently.

• I really appreciate your comment about “being in solitude” – I think many people underestimate the impact that environment has on their thinking process, and finding the right environment for doing serious mental work can have a huge affect on how productive you are! It’s also worth noting that different people need different levels of stimulation – so for some, a noisy place might provide just the right situation for good thinking (provide the noise is background, and not distracting).

8. Proposition: For any string $s$, $s$ has a solution if and only if the amount of I’s within is $s$ is not divisible by 3.

Here is a link to my proof

• Adam, I commend you for a most thorough investigation of the MIU puzzle. Anyone interested in a detailed and (surprisingly!) complete solution to the puzzle is encouraged to take a look. Sweet!

9. 1. I think that the conjecture is false.
2. At first I thought that the conjecture was true because if you start with MI then you could double the string after I making it MII and continuously make it a long string of I’s after the M, then substitute the U’s from III. However, I put in some logic that if you continually double the I’s you would always have an even number of I’s. So suppose you wanted a string with an odd number of I’s and U’s, then you would be out of luck and not be able to solve the puzzle by doubling the I’s. for example Goal Word: MIIU
Start: MI
MII (rule 2)
MIIII(rule 2)
MIU (rule 3) Here we cant solve this by just Doubling I. even if we choose to double I once more making it MIIIIIIII and substitute 6 I’s making it MIIUU and then deleting the two U’s we would have MII, then we would be back to what we started with MII.

2. I used my own logic and intuition to try to figure out my answer that the conjecture is false due to the lack of internet connection in my house.
3. During my lunch/dinner break at work I spent the whole time trying to figure the puzzle out, until I talked to other co-workers about it and they got somewhat interested for a moment and they tried to convince me that that the conjecture was true and it led me to think even more about it to prove them wrong.

• Oh, and I numbered the questions wrong, the last one was supposed to be an answer to question 4 and the second to last was supposed to be the answer to number 3.

• Arguing with other people about math is one of the best ways to attack math! I’m curious to know – what is your job? Not everyone has co-workers who would be interested in the MIU puzzle…

(I do think that MIIUU is a possible string, though – can you figure out how to get it?)

10. I believe that this was true. Can I prove that it this is true but I do have a valid reasoning of why I think this is true. The reason is if you try enough steps then you will eventually get the MI. For example there was a ted talk about infinity. That there are different size sets. The reason why this connects is because you will never know how many times you apply a different rule you may get MI.

11. 1. I think the conjecture is false.
2. When I worked on this assignment, I tried to first solve Denice’s MIU puzzle after about 4 sheets of paper I gave up because I couldn’t solve it. I saw that Saloua’s puzzle was similar to Denice’s so I thought hey let me try to do Saloua’s puzzle instead. Boy was I wrong that thinking to do this. I also tried to Google the puzzle to see if by any chance the correct solution would be posted. All I found was more literature on how to do the MIU puzzles, which helped a bit. While working on Saloua’s puzzle, it helped me solve Denice’s puzzle funny enough. I’m not sure which step I messed up on but by working on Saloua’s puzzle about 10 times I finally got the enough steps to go back to Denice’s puzzle and solve her puzzle. I also had to step away and regroup after failing miserably at trying to solve Saloua’s puzzle. I think by stepping away and then going back to the original puzzle I wanted to solve helped me to solve it.
3. I used a lot of paper and luckily I didn’t have to spend any money on the paper (the honor’s room has a bunch of scrap paper in box), I also used the internet, I tried to Google more information on the MIU puzzle which helped me to eventually solve the once unsolvable problem Denice posted but it didn’t help with Saloua’s problem. I still believe Saloua’s puzzle is unsolvable.
4. The activity that I think was most useful was the paper and my pencil. I think it’s never smart to try to work on problems with a pen (my opinion of course). The amount of erasing and crossing out that I did was insane. I think by taking a break also helped me to finally reach the problem. At one point I had to step away to clear my head and when I go back and tried to work on Denice’s problem again I finally figured it out. I think by working on it helped and starting over helped to figure out the answer.