You are here: Directory > Mathematics > Article

# The Value of 'Impossible' Problems

One 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

'MUIUUIU') - 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?

# Member Comments

I would very much like to see a proof of the impossibility of that puzzle!

But that would spoil the fun!

could you at least give me a HINT?

I'll give you a one word hint:

**modulus**
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?

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?

Yeah, that does make sense.

I'll have to play around with that.

I'll have to play around with that.

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 2

Now apply rule #2 m times. The number of I's is now:

2

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?

Suppose you begin with k I's. If you do rule #3 n times, the number of I's is now 2

^{n}k.Now apply rule #2 m times. The number of I's is now:

2

^{n}k - 3mThe 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?

yeah, humphrey, I think that's more or less that attack I used.

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:

Isn't that interesting?

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?

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

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

# Submit a comment

Please keep comments courteous and on-topic. All comments are moderated by the article author.

# Common Destinations

Click 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.