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.
The induction argument fails when k+1 = 2, because the argument presumes the presence of at least three dogs to work. Here's why:
Let's name the subgroup of k dogs which does not contain x to be S1 and the second subgroup of dogs (which does contain x) to be S2. Now by induction we know that all dogs in S1 are the same color; similarly we know that all dogs in S2 are the same color. However, in order to conclude that the dogs in S1 are the same color as the dogs in S2, there needs to be a third dog that is in both groups. That doesn't happen when k+1 is 2. S1 contains just the one other dog. When we form S2, we can only include x. So S1 and S2 are perfectly fine, uni-colored sets of dogs. But we can't conclude that the color of S1 is the same as the color of S2 in this instance because there is no dog contained in both sets.
dogged logic
