|
|
Impossible Problems - Comments and DiscussionThis is the comment and discussion page for the article The Value of 'Impossible' Problems, published in Directory : Mathematics.
|
|
|
|
Humphrey Nowlin says:
I would very much like to see a proof of the impossibility of that puzzle!
Douglas Twitchell says:
But that would spoil the fun!  
Humphrey Nowlin says:
could you at least give me a HINT?
Douglas Twitchell says:
I'll give you a one word hint: modulus
Marcus J. says:
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 says:
Yeah, that does make sense.
I'll have to play around with that.
Humphrey Nowlin says:
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 says:
yeah, humphrey, I think that's more or less that attack I used.
MisterQ says:
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 says:
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
|
|
|
|
|
While site upgrades are in progress, the commenting feature has been disabled. We apologize for any inconvenience.
|
|
|
|
|
Member Options
Other Categories
|
|
