The Value of 'Impossible' ProblemsOne day, back when I was a high school student, a friend handed me a puzzle book. "Doug," he said, "I can't figure this puzzle out. I've been working on it forever. You want to take a look at it?"
So I took the book from him and read the problem. I tinkered with it for quite a while, then started laughing. "What?" he asked.
"Jeff, the reason you can't solve the problem is because it can't be solved." Of course, Jeff was very annoyed. I proceeded to write a proof that the problem could not be solved. Below is the problem, as it was stated in the puzzle book. I am not providing my 'solution'--I will leave that for you to figure out.
Change the string of letters 'MI' to the string 'MU',
using the following rules.
- If a string ends with 'I', 'U' can be added ('MI'
can be changed to 'MIU')
- Three 'I's in succession can be changed to a 'U'
('MUIII' can be changed to 'MUU')
- The string 'Mx' (where x is any sequence of
letters) can be changed to 'Mxx' ('MUIU' can be changed to
- Two 'U's in succession can be deleted ('MIUU' can
be changed to 'MI')
Okay, so it's a cruel thing to give a student an unsolvable problem, without warning him it's unsolvable. But at the same time, isn't that how real life is?
When Orville and Wilber set out to build an airplane, did they know that it could be done? How advanced would we be technologically if everyone said "I don't know if it can be done, so I'm not going to waste my time trying."
Curiosity and a willingness to experiment are traits that we need to instill in our students. Tomorrow's scientists and researchers are in our classrooms today. Some of the best words for them to hear from their teachers are "I don't know if this can be done, but why don't you see if..."
I still remember the day my high school physics teacher handed me and my friend Mike a thermometer and a computer, and said, "See if you can make the computer read the thermometer." I immediately asked if he knew how to do it. (I was suspicious, because my physics teacher was famous for just making things up on the spot) He said, "Oh, I'm sure it can be done, I just don't know how."
Here are a few 'impossible' problems (only a few of them are truly impossible) to set your advanced students working on. Some of these I know can be done, because I've done them myself. Others I've either tried and failed, or never tried at all. Some, like the first problem above, I know can't be done. But if you have students who are interested in trying, think of the mathematics they might learn in the process of attempting these!
Can you create a cubic formula? (Like the quadratic, only for solving cubic equations)
- What about a quartic formula (fourth degree)?
- Can you trisect an angle using just a compass and straight edge?
Can you generate a method for finding the inverse
of an NxN matrix?
- Can you draw a map in which each bordering region is a different color, and the map requires more than 4 colors?
- Can you determine whether the series 1/2 + 1/3 + 1/4 + ... converges or diverges?
- Can you find two irrational square roots, the sum of which is an integer?
- Can you generate a formula which will give you all the pythagorean triples?
- Can you create a formula for the sum of the first N perfect squares? What about perfect cubes?
- Does the ratio of (primes less than N) to (composites less than N) approach a limit as N goes to infinity?
Comment by Humphrey Nowlin on Feb 25, 2005I would very much like to see a proof of the impossibility of that puzzle!
Comment by Douglas Twitchell on Feb 25, 2005But that would spoil the fun!
Comment by Humphrey Nowlin on Feb 26, 2005could you at least give me a HINT?
Comment by Douglas Twitchell on Feb 26, 2005I'll give you a one word hint: modulus
Comment by Marcus J. on Mar 7, 2005Okay, so there are two rules that effect the number of "I's" in the string.
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?
Comment by Humphrey Nowlin on Mar 8, 2005Yeah, that does make sense.
I'll have to play around with that.
Comment by Humphrey Nowlin on Mar 9, 2005Okay, 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?
Comment by Douglas Twitchell on Mar 11, 2005yeah, humphrey, I think that's more or less that attack I used.
Comment by MisterQ on Mar 13, 2005Hi there,
I thought you might like to know this quote by John Stuart Mill, which goes very nicely with your article about "impossible" problems:
A pupil from whom nothing is ever demanded that he cannot do, never does all he can.
Isn't that interesting?
Comment by Michael Dehmlow on Nov 4, 2005Here 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.
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 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:
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)
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:
must show: 1+3*(k+1) =2^m-3z
No mater what x we choose 3x+1?y/3 where y is an element of the integers.
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.
Please keep comments courteous and on-topic. All comments are moderated by the article author.
Common DestinationsClick an icon below for some of the commonly accessed pages at Articles for Educators
Click here to read questions submitted by other teachers, and help them out from your own experiences.
Write up a lesson plan, or just a paragraph or two about your favorite teaching trick.
Articles for Educators provides high quality resources for teachers, administrators and students.