Math Is Fun Forum

ezaspi

Member

Registered: 2005-08-01

Posts: 9

The MU Puzzle

I am currently reading "Godel, Escher, Bach:  an Eternal Golden Braid".  It is a book that, at least so far, attempts to explain Godel's Incompleteness Theorem, among other things about seeking "truth" or a perfect set of axioms.  It's very interesting.  Has anyone else read it? What are your thoughts?

Anyway, this post is about a particular puzzle that is given at the first of the book.  I have not finished the book, so I'm not sure whether or not there is a solution; however, I thought everyone might enjoy churning over it.

So, here it is:

1.  Begin with the string 'MI'.

2.  Now, you can modify your string at any point according to the following rules:

2a.  If your string ends in an 'I', you can add a 'U' to the end of it.
2b.  If your string is of the form M{therest}, you can add {therest} to the end, creating M{therest}{therest}.
2c.  If your string contains 'III', the 'III' can be replaced with a 'U'.
2d.  If your string contains 'UU', the 'UU' can be dropped.

3.  Use the rules above and change 'MI' into 'MU'.

To make sure that it's clear, here is a possible way to apply the rules:

MI -> MII (rule 2b) -> MIIII (rule 2b) -> MIIIIU (rule 2a) -> MIUU (rule 2c) -> MI (rule 2d)

Can you get 'MU'?

Anyway, I have my own thoughts about the answer to the above question, but I will withhold them temporarily as to not color your own investigations. 

The discussion around the puzzle is very interesting as well, since it is given specifically to teach about axioms, theorems, etc., but perhaps I will save that for another thread...

---

Have your pi and e it, too!
http://www.pidye.com

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: The MU Puzzle

What is {therest}?

I assume this is somehow wrong:

MI -> MII -> MIII -> MU

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: The MU Puzzle

I think {therest} is the whole chain apart from the first M. So your second step is wrong because you need to add II instead of I.

Interesting puzzle though. It doesn't look trivial to prove either way.

---

Why did the vector cross the road?
It wanted to be normal.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: The MU Puzzle

My thoughts:

Edit: I think this may prove it:

---

Why did the vector cross the road?
It wanted to be normal.

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: The MU Puzzle

Thats crazy! I got this book for christmas from a relative! The book is yellowed with age though. I'm suprised someone else has it. I'm sort of reading bits and pieces of it. Some of the stuff is really confusing, other stuff is just plain interesting!

---

A logarithm is just a misspelled algorithm.

ezaspi

Member

Registered: 2005-08-01

Posts: 9

Re: The MU Puzzle

mathsyperson -

You are correct.  You must double the entire string succeeding the 'M' when applying rule 2:

MIUIIUIU -> MIUIIUIUIUIIUIU when applying rule 2
MIIUUI -> MIIUUIIIUUI when applying rule 2

etc.

---

Have your pi and e it, too!
http://www.pidye.com

ezaspi

Member

Registered: 2005-08-01

Posts: 9

Re: The MU Puzzle

mathsyperson -

I believe that your analysis is correct.  Or, those match my own thoughts, anyway.

---

Have your pi and e it, too!
http://www.pidye.com