What is the solution to the MI string puzzle?

  • Context: Undergrad 
  • Thread starter Thread starter croxbearer
  • Start date Start date
  • Tags Tags
    Puzzle String
Click For Summary

Discussion Overview

The discussion revolves around a logic and mathematics puzzle involving string manipulation based on specific transformation rules. Participants explore whether it is possible to produce a string containing exactly the characters "MU" from an initial string of "MI" while adhering to the given rules.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant outlines the transformation rules for manipulating the string starting with "MI" and proposes the goal of producing a string containing "MU".
  • Another participant demonstrates a sequence of transformations leading to a string that contains "MU" but asserts that it is impossible to reach "MU" as a final result.
  • A subsequent post rephrases the question to clarify the goal of producing exactly "MU".
  • One participant argues that it is impossible to achieve a string without at least one "I", citing a modular arithmetic argument regarding the number of "I's".
  • Another participant suggests that doubling the characters can lead to more "I's", implying that the number of "I's" can increase indefinitely.
  • One participant notes that while it is possible to reach certain configurations of "I's", they acknowledge a limitation in reaching a state with zero "I's" based on the doubling rule.
  • Another participant clarifies that the minimum number of "I's" that can remain is one, but does not rule out the possibility of having two "I's".

Areas of Agreement / Disagreement

Participants express disagreement regarding the possibility of achieving the string "MU". While some argue it is impossible to eliminate all "I's", others suggest that various configurations can be reached, leading to uncertainty about the final outcome.

Contextual Notes

Participants reference modular arithmetic and the effects of the transformation rules on the count of "I's", indicating that the discussion is limited by these mathematical considerations and assumptions about the rules.

croxbearer
Messages
18
Reaction score
0
I don't know if you have encountered this problem in Logic and Mathematics. Anyway, you may try this:

You are given with an initial string of MI.

Here are the rules:

i) If you have a string that ends with I you can add a U
ii) If you have an Mx, (i.e., an a string that starts with an M, with other characters succeeding it) you can double the characters succeeding the M, i.e., you may lengthen your string by writing Mxx
ii) If you have an III part on your string, you may replace it with a U
iv) If you have a UU in your string, you can drop this altogether, i.e., starting with an MUUU, you can drop the UU, to get MU.

Now, the question is: Could you produce a string containing the characters, MU? (without of course trespassing the bounds of the rules)
 
Mathematics news on Phys.org
YES!
initial string "MI"
(rule 2) -> "MII"
(rule 2) -> "MIIII"
(rule 3) -> "MUI" : this string contains the characters MU !

But it's impossible to get the string "MU" as final result.
 
I am sorry. May I rephrase the question with:

Could you produce a string containing exactly the characters, MU?
 
croxbearer said:
I am sorry. May I rephrase the question with:

Could you produce a string containing exactly the characters, MU?


Obviously not, since you can never get a string that does not contain at least one I.

Proof:
Consdier how the various operations alter the number of I's mod 3:
1,3, and 4 do not change it at all, and 2 multiplies the total number of I's by two.
Thus you cannot get from a string that has a number of I's that is not zero mod 3 to one that is. Specificall you cannot get from a string that contains one I to one that contains zero.
 
You can double the x where [tex]M_x[/tex]

3I is equal to U

[tex]\frac{2^n}{3}[/tex]

You are doomed to end up with 1 "I" remaining..
 
It is possible to get MIIIII (5 I's) so why shouldn't it be possible to get more numbers?

mi->mii->miiii->miiiiiiii->miiiiiiiu->miiiiiuu->miiiii
 
Last edited:
OK I think i see it now, It seems to be impossible to get to 3 from 1 by doubling, i can get any number mod 3 = 1 or 2.
 
Oh i was trying to say minimum # of I can only be 1, i didn't mean to rule out "2"
 

Similar threads

Comp Sci Complexity for generating strings of length k from CNF grammar
  • · Replies 3 ·
Replies
3
Views
2K
Graduate What are your insights on The Hardest Logic Puzzle Ever?
  • · Replies 2 ·
Replies
2
Views
3K
Graduate What is the Best Resource for Learning String Theory as a Side Project?
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Open string end points, their motion in spacetime
  • · Replies 3 ·
Replies
3
Views
3K
What is the solution for a string under tension with given boundary conditions?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Trying To Conceptualize Two Dimensions Of Time
  • · Replies 2 ·
Replies
2
Views
6K
Undergrad How Do Waves Propagate on a String?
  • · Replies 0 ·
Replies
0
Views
5K
Undergrad What are the Priority Tasks for High Energy Physics Beyond the Standard Model?
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Testing string/m-theory extra dimensions prediction
  • · Replies 10 ·
Replies
10
Views
4K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K