(page 1001(2))
|
|
(page 1001(2)) |
|
| Proving all Horses are the Same Colour | |||||||||
|
You must be careful with proof by induction.
If you google for "proving all horses are
the same color [sic]"
you will find hundreds of proofs that all horses are the same colour.
Basically these proofs go as follows.
Let the idea be: Idea(n) is that in a corral of n horses all the horses are the same colour.
Step I |
Obviously if there is only one horse, then all horses in
the corral have the same colour, so Idea(1) is true.
| Step II |
Assume that Idea(k) is true for some k.
| Step III |
Assume that we have a corral of k horses and an extra horse.
| Take one horse out of the corral and add the extra horse. Given there are still k horses in the corral they must all be the same colour, and since the horse that we removed was the same colour as the horses that were left in the corral, and the horses that were left in the corral are the same colour as the horse that was added, the horse that was removed must be the same colour as the horse that was added. Therefore all horses are the same colour. So what's wrong? |
Do you see what's wrong?
| What if the k assumed in step II was 1. When we removed one horse from the corral, the corral would have been empty. So the added horse is going to have the same colour as the other horses as there aren't any, but it doesn't mean that the added horse has the same colour as the horse that was taken out of the corral. So our proof in step III is faulty, hence our idea is not proved. |
| hanoi09.qh - 1.4 - 05/10/02 |
|