False Proof – All Horses are the Same Color

Problem: Show that all horses are of the same color.

“Solution”: We will show, by induction, that for any set of n horses, every horse in that set has the same color. Suppose n=1, this is obviously true. Now suppose for all sets of n horses, every horse in the set has the same color. Consider any set H of n+1 horses. We may pick a horse at random, h_1 \in H, and remove it from the set, getting a set of n horses. By the inductive hypothesis, all of the n remaining horses are the same color.

On the other hand, if we remove a different horse h_2 \in H, we again get a set of n horses which are all the same color. Let us call this color “brown,” just to give it a name. In particular, h_1 is brown. But when we removed h_1, we got that all the remaining horses had the same color as h_2. So h_2 must also be brown. Hence, all horses in H are brown.

Explanation: The argument here is valid for almost all n. For large n, it is a very natural argument that follows from the inductive hypothesis. However, it fails for n=2 (and this is the only time it fails). By having only two horses, we cannot conclude that the removed horses have the same color, because there aren’t any horses remaining in H to apply the transitivity of “having the same color as.”

This false proof highlights the danger of neglecting the base case of an inductive argument. Here the true base case was not n=1, but rather n=2. Since the base case is false, we should have prudently stopped our argument there before embarrassing ourselves.

Advertisements

7 thoughts on “False Proof – All Horses are the Same Color

  1. I enjoyed your “proof”, but I’d suggest a revision to the reason it’s invalid. I don’t think it’s so much that you need to consider the case of 2 horses. What the proof does, is not the normal sort of induction that I’ve seen. Typically you show it’s true for n=1 (which in the horse proof is trivial). Then you assume that it’s true for n, and then show that this means it’s true for n+1. You can’t do that in this horse of a different color proof. If you assume it’s true for n, you really don’t have any way of getting to n+1. To start by assuming that it’s true for ANY collection of n+1, you’re begging the question.

    In any case, I still have to say that I enjoyed reading it.

    Like

    • The proof fails for n=2 because the general argument works precisely when there are at least three horses. In particular, there has to be a horse which was not removed in order to conclude that the two removed horses share its color. Rest assured that this is a standard induction argument, and I don’t assume anything about the set of n+1 horses (H in the above proof).

      So in fact, if it were true that any set of n = 3 horses is unicolored, then it would be true that any set of n > 3 horses is unicolored.

      Like

  2. You’re right, I misread your “proof”. For some reason I thought I read that you started with the assumption about n+1 horses. Must have been before I had my coffee.

    Like

  3. @mitchellkaplan You actually hinted at another common mistake with induction (not sure if j2kun has another false proof demonstrating it):

    1. Take the case with n+1
    2. Reduce it to the case with n (incorrectly!)
    3. Apply the induction hypothesis on the reduced case
    4. Expand the case with n to the case with n + 1

    For example, I remember seeing this in graph-related proofs where you would remove a node from the graph except the resulting graph didn’t satisfy certain constraints (and hence the induction hypothesis did not apply to it!).

    Another similar mistake is to take the n case and make the erroneous claim that every n+1 case can be extended from a n case. I also saw this with respect to graphs where not every graph with constraint “Foo” and n+1 nodes could be constructed from a graph with constraint “Foo” and n nodes.

    Induction’s pretty hard? 🙂

    Like

  4. Before I read the explanation, I had deduced that the problem was with the case of n = 1, because you need at least two different things in order for “same as” to make sense. (Never trust a proof that uses “obviously” or trivially”.)

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s