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.

(In reply to solution by Charlie)

I interpret "Same" like congruent... So "same color" means that the colors are the same. And since a dog can't be red and green at the same time, it can't be the same as both red and green dogs.

I agree with what you said with colors, but I don't understand how this would relate to the problem. If k is greater than 1, than at least one dog in the old subgroup (without x) is in the new subgroup (with x)

When I see that, I just see you swapping out another dog for x in the old subgroup to get the new subgroup.

If the problem is in the wording, couldn't you just switch my definition for same into the problem, and it would still read with a problem?

Posted by Gamer on 2003-05-30 10:41:28