Induction justification (Algorithms)?

Question

The following induction "justification" that all sheep in a flock are the same color is wrong. I have to state what makes it wrong.

Base case:
One sheep, It is clearly the same color as itself

Induction step:
A flock of n sheep. Take a sheep, a, out of the flock. The remaning n-1 are all the same color by induction. Now put sheep a back in the flock, and take out a different sheep, b. By induction, the n-1 sheep are all the same color. Therefore, a is the same color as all the other sheep; hence all the sheep in the flock are the same color.

I have two ideas which i am working with

The base case states that only one sheep by itself is the same color. I can take a group of sheep and separate them. They can be all the different color, but by the base case they are considered the same.

In the induction step there is no comparison amoung the sheep. In order to tell if they are the same there should be a comparsion between them.

Still thinking about it. Any ideas?

Answer 1

Seems to me the induction fails when n = 2.

Take a sheep out, and the one sheep is the same color as itself. Take the other sheep out and the remaining sheep is the same color as itself.

But, the two sheep need not be the same color.

In particular the statement

>>Therefore, a is the same color as all the other sheep; hence all the sheep in the flock are the same color.

Is false.