| Humphrey Nowlin wrote on Feb 25, 2005 |
quote options |
| I would very much like to see a proof of the impossibility of that puzzle!
|
| Douglas Twitchell wrote on Feb 25, 2005 |
quote options |
But that would spoil the fun!  
|
| Humphrey Nowlin wrote on Feb 26, 2005 |
quote options |
| could you at least give me a HINT?
|
| Douglas Twitchell wrote on Feb 26, 2005 |
quote options |
| I'll give you a one word hint: modulus
|
| Marcus J. wrote on Mar 7, 2005 |
quote options |
Okay, so there are two rules that effect the number of "I's" in the string.
Three 'I's in succession can be changed to a 'U'
The string 'Mx' (where x is any sequence of letters) can be changed to 'Mxx'
One rule subtracts 3 from the number of I's. The other multiplies the number of I's by two.
So if you could show that no combination of those two rules gets rid of all the I's, the proof would be complete, right?
|
| Humphrey Nowlin wrote on Mar 8, 2005 |
quote options |
Yeah, that does make sense.
I'll have to play around with that.
|
| Humphrey Nowlin wrote on Mar 9, 2005 |
quote options |
Okay, here's what I came up with...
Suppose you begin with k I's. If you do rule #3 n times, the number of I's is now 2nk.
Now apply rule #2 m times. The number of I's is now:
2nk - 3m
The only way this is a multiple of 3 is if k is a multiple of three, which it is not (k=1), and since 0 is a multiple of three, you cannot get zero I's.
Of course, now that you've applied rule 3 n times and rule 2 m times, you have a different number of I's, but this is also not a multiple of 3, so we can repeat the above adnauseum.
I know, I've done a lot of hand waving, but that's my rough proof. What do you think?
|
| Douglas Twitchell wrote on Mar 11, 2005 |
quote options |
| yeah, humphrey, I think that's more or less that attack I used.
|
| MisterQ wrote on Mar 13, 2005 |
quote options |
Hi there,
I thought you might like to know this quote by John Stuart Mill, which goes very nicely with your article about "impossible" problems:
Quote
A pupil from whom nothing is ever demanded that he cannot do, never does all he can.
Isn't that interesting?
|
| Michael Dehmlow wrote on Nov 4, 2005 |
quote options |
Here is a semi formal proof of the mi/mu problem:
It is impossible here is why:
We need 0 i's to produce "mu" the only way we can eliminate all i's
is to have a multiple of three them and turing them into a u's. Since the only rule that actually makes less i's is to eliminate three of them in the rule iii->u.
However
The only operation we can perfrom on i's is to subtract three of them
or a double them since we have one i to begin with we have 2^n i's or
2^n-3x i's
But:
2^n will yeild a prime factorization of all 2's (thus not divisible
by three). We can either subtract 6 (replace iii iii with u u and
eliminate) or we can subtract three(add a U to the end and make the
last iii into a u and eliminate).
so the possible values of the length of i are 2^n :
1 2 4 8 16:
or 2^n-3y:
1 2 4 7 10 13 16 19 22 25 28 31 34...
but we can never get a a multiple of three out of the superset of 2^n-3y and 2^n
(note 2^n is a subset of 2^n-3y)
part a
For every 2^n-3y we will get a number that is in the sequence. 1 2 4 7
10 13 16 19 22 25 28 31 34... which is 1 +3*x.
so for every x there exist some y and n such that 1+3*x =2^n-3y.
proof by induction:
x=2
1+3*2=7
2^4-3*3=7
16-9=7
assume:
1+3*k =2^n-3y
must show: 1+3*(k+1) =2^m-3z
y-1=z
1+3k+3=2^(m)-3(y-1)
m=n
1+3k+3=2^(n)-3(y-1)
1+3k+3=2^n-3z+3
1+3k=2^n-3z
QED
Part B:
No mater what x we choose 3x+1?y/3 where y is an element of the integers.
proof:
3x+1=3y
x+1/3=y
Since the set of integers is closed there is no whole number x that
when you add one third to it you will get a whole number.
QED
-edited by Michael Dehmlow on Nov 4, 2005
|
