Least Difference and MIMU

  1. Take the ten digits from zero to nine. Arrange them in two numbers. Subtract the smaller number from the larger one to get the least possible difference.

  2. Consider the following four rules:
    1. You can add 'I' at the end of a string ending with 'U'
    2. If you have a string Mx you can write the string Mxx
    3. Whenever you find a 'III' you can turn it into 'U'
    4. Whenever you find a 'UU' you can remove it from the string
    Are you able to turn MI into MU?
Source: 1. NPR puzzle for July 16, 1995., 2. rec.puzzles Nov. 21, 1996.
Solutions were received from Robert McQuaid, Al Zimmermann, Denis Borris, Joseph DeVincentis, Le Ba Nguyen, Dave Bachtel, Mark Meyer, Henry Bottmley, Richard Winterstein, Kirk Bresniker, Ravi Subramanian, Sandy Thompson, Michael Moyer, and Philippe Fondanaiche. The solutions are:
  1. The expected numbers were 50123 and 49876, with a difference of 247. But special recognition to Dave Bachtel, who submitted a pair of numbers with a smaller difference. They're acceptable, given the way the problem was phrased:
            0
    98765432    and   1

  2.    MI
       MII             rule 2
       MIIII           rule 2
       MIIIIIIII       rule 2
       MIIIIIU         rule 3
       MIIUU           rule 3
       MIIUUI          rule 1
       MIII            rule 4
       MU              rule 3
    Many thanks to several solvers who pointed out that this problem is very similar to one posed in Douglas Hofstadter's Godel, Escher, Bach. In that book, rule 1 was changed to read "You can add 'U' at the end of a string ending with 'I'". In this case, the problem is not solvable. A few people sent proofs of that, but I'll leave it unproven here for others to think about.

Mail to Ken