Find the mistake in the following proof that all dogs are the same color (if there's any):

Let's use induction. Consider groups of 1 dog. All dogs of every group are the same color, of course. So we now that it's true for 1. Suppose it's true for groups of k dogs, i.e. every group of k dogs are the same color. Then let's consider any group A of k+1 dogs. Consider a subgroup of A containing k dogs. Let's call x the dog in A but not in the subgroup. Then by induction, all dogs in the subgroup are the same color. Now consider a subroup of A of k dogs, with x in the subgroup. All dogs except for x are the same color. Then, since every group of k dogs are the same color (by induction), all dogs in A are the same color. So x and every dog are the same color.

This makes absolutely no sense to me. It sounds like you're saying that if you have multiple groups of one dog each, all dogs in each group would be the same color, which is obvious. But k dogs? Is k a variable? You can't just suppose that it's true for any random number of dogs just because it's true for one dog.
Then, when you get the a group A of k+1 dogs you've lost me completely =/

Posted by michelle on 2003-11-11 18:17:03