All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 All dogs are the same color! (Posted on 2003-05-30)
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.

 See The Solution Submitted by Fernando Rating: 3.5000 (10 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 k = 1 | Comment 22 of 23 |

P(n) denotes "All dogs in a set of order n are the same color".<br>

Clearly, the basis step P(1) is true.<br>

For the induction step we have a set S with |S| = k+1 and we wish to prove there exists subsets, S1 and S2, of S such that<br>

(1) |S1| = |S2| = k<br>

(2) Union(S1,S2) = S<br>

(3) Intersection(S1,S2) is not empty<br>

This holds for all k > 1. But, for the induction step to work it must hold for k = 1 also.<br>

Let S = {a,b}. Power-set(S) = { empty , {a} , {b} , S }.<br>

S and the empty subset fail (1).<br>

{a} and {b} pass (1) and (2), but fail {3}.<br>

Therefore, all we can say is P(1) is true.<br>

I first saw this thirty years ago in an abstract algebra class. I think it was an exercise in  the book "Algebra" by MacLane and Birkoff.<br>

 Posted by Bractals on 2005-02-16 01:15:35

 Search: Search body:
Forums (0)