# Whats wrong with this proof?

Arjun Shastry

Ranch Hand

Posts: 1903

1

posted 13 years ago

Theorem: All horses are of the same colour.

Proof: We prove this by induction on the number of horses in a group.

For n = 1, there is only one horse and hence nothing to prove.

Assume that given any group of n horses, all are of the same colour.

To prove the above statement for n + 1, consider a group of n + 1 horses.

Remove one horse from the group. Then, by assumption, remaining n horses

are of the same colour. Replace the horse and remove another one from the

group. Now the remaining n are of the same colour. Hence all the n + 1 horses are of the same colour.

[ October 15, 2003: Message edited by: Capablanca Kepler ]

Proof: We prove this by induction on the number of horses in a group.

For n = 1, there is only one horse and hence nothing to prove.

Assume that given any group of n horses, all are of the same colour.

To prove the above statement for n + 1, consider a group of n + 1 horses.

Remove one horse from the group. Then, by assumption, remaining n horses

are of the same colour. Replace the horse and remove another one from the

group. Now the remaining n are of the same colour. Hence all the n + 1 horses are of the same colour.

[ October 15, 2003: Message edited by: Capablanca Kepler ]

MH

posted 13 years ago

This is easy. It fails when we have two horses.

remove 1 horse. we have one left, and it must be the same color as itself.

replace that one, and remove the other. it must be the same color as itself.

BUT, there is nothing connecting the two sets togther. you have not proved that there is a RELATIONSHIP between the two groups.

in other words, the color of one horse has no bearing on the color of another.

[ October 16, 2003: Message edited by: fred rosenberger ]

remove 1 horse. we have one left, and it must be the same color as itself.

replace that one, and remove the other. it must be the same color as itself.

BUT, there is nothing connecting the two sets togther. you have not proved that there is a RELATIONSHIP between the two groups.

in other words, the color of one horse has no bearing on the color of another.

[ October 16, 2003: Message edited by: fred rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors