Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#1 2013-05-02 00:44:13

Agnishom
Real Member
Award: Wink Sherlock

Offline

Colored Horses



Theorem If A is a set of horses, then all the horses in A have the same color.


Proof Let S be the statement, "If A is the set of n horses, then all the horses in A are of the same color."
Clearly S is a statement concerning positive integers.

(1) S is true for n = 1.

Rephrased, it tells that "If A is a set of 1 horse, then all the horses in A have the same color."
Obviously, this is true.

(2) If S is true for n = k, then S is true for n = k + 1.

The horses can be numbered from 1 to k + 1. For the sake of convention, let this be already done.
Removing Horse #1, we are left with k horses. We are already assured that a set of k horses have the horses colored in a similar way. Therefore, Color of Horse #2 = Color of Horse #3 = Color of Horse #4 = ... =Color of Horse #(k+1)
On the Other hand and with the same arguments, removing Horse #(k+1) would yield: Color of Horse #1 = Color of Horse #2 = Color of Horse #3 = ... =Color of Horse #k
Therefore, Color of Horse #1 = Color of Horse #2 = Color of Horse #3 =....=Color of Horse #(k+1).
So S is true for n = k + 1, given that S is true for n = k

Invoking the principle of induction, (1) and (2) proves S is true for all positive integers.
Therefore, the Theorem is true. Q.E.D.

Corollary All the horses in the universe are of the same color.

Proof Let A be the set of all horses in the Universe. Therefore, by the Theorem, all the horses in the universe are of the same color.



Source: Dots and Lines by Richard J. Trudeau


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#2 2013-05-02 02:16:27

SteveB
Power Member

Offline

Re: Colored Horses

(2) If S is true for n = k, then S is true for n = k + 1.

The horses can be numbered from 1 to k + 1.

I think that the flaw in the argument is that you have to start by assuming that it is true for n=k then show that it follows
that it is true for n=k+1.

The statement "The horses can be numbered from 1 to k + 1" means that you are cheating by assuming that the statement is
true for n=k+1 and then "proving" that it is true for n=k+1

The horses can only be numbered from 1 to k. So when you add the k+1st horse it can of course be different.

For the sake of convention, let this be already done.
Removing Horse #1, we are left with k horses.

So here, we are only left with k-1 horses. We now have to add two horses to get to k+1
One of these is the same color, but the other might not be.

(At least that is what I think. I wonder what the more experienced MIF users think of this problem.)

 

#3 2013-05-02 03:31:39

SteveB
Power Member

Offline

Re: Colored Horses

I have thought of another idea for what is wrong:

Are we saying that the hypothesis is true for all sets of horses of that size of of just one particular horse set size?

There is a big difference between "I have one set of one horse which is the same color as itself"
to "All pairwise comparisons of pairs of horses have the same color".

Take the basis case n=1. If we take the first statement to be the interpretation then it is true because we are only comparing
the horse with itself.

However it is nonsense in the second interpretation: If all pairs of sets of horses with n=1 have to be the same color for the basis
case to be true then the basis case is not true.

Are we trying to argue to get from n=1 to n=2 that given that a horse is the same color as itself then if we look at the set
containing both horses take away one horse it is the same as itself therefore n=2 works?

There is an inconsistent phrase in the theorem of "the" set of horses as compared to "a" set of horses. This is a big difference.
Either n=1 just has to represent one isolated set of one horse, or it has to represent every set including every pairwise comparison
between two sets to be valid, otherwise the inductive step will not be valid.

I think that the case for n=1 probably is supposed to be that each horse however chosen is the same color as itself.
However the n=2 case would be that any pair of horses however chosen are the same color.
We obviously cannot get from n=1 to n=2 so there has to be a flaw. If we have two horses {horse1, horse2} then
remove n=1 of them we get {horse1} or {horse2} either way the inductive step from n=1 to n=2 will not be proven.
The fact that the hypothesis holds for the sets individually does not tell us anything about the pairwise comparison between
the two horses. If we number the set from 1 to (2-1) then this is 1 to 1 ie horse1. If we number them from 2 to 2 then this
is horse2. Of course if we could prove the hypothesis for the case n=2 then we would have proven it for all n because if we
can arbitarily choose any pair and show that they have the same color then all horses are the same color.
So yes my revised answer would be that we cannot get from n=1 to n=2. This assumes the interpretation that we are
taking ANY pair of horses for n=2 and not just one isolated set. (If it is an isolated set then all of the n=k to n=k+1
steps are flawed, because we are always taking in a new horse that we don't know anything about.)
The inductive step could be said to work from n=2 to n=3 because each pair is covered by the n=2 case, but if you
go through the inductive step for n=1 to n=2 then of course it is nonsense, because there is no overlap between the
one size smaller subsets of {horse1, horse2}.

Last edited by SteveB (2013-05-02 05:31:53)

 

#4 2013-05-02 14:06:41

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Colored Horses

I think that the flaw in the argument is that you have to start by assuming that it is true for n=k then show that it follows
that it is true for n=k+1.

The statement "The horses can be numbered from 1 to k + 1" means that you are cheating by assuming that the statement is
true for n=k+1 and then "proving" that it is true for n=k+1

The horses can only be numbered from 1 to k. So when you add the k+1st horse it can of course be different.

We know there are k + 1 horses, we can number them from 1 to k+1 always, even if they are not of the same color


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#5 2013-05-02 17:19:54

SteveB
Power Member

Offline

Re: Colored Horses

Yes I agree with you there. My first post was not really the point where the argument fails.

The problem is not where we take an arbitrary set of size k + 1, but rather the point in my second post.

The inductive step only works if we can argue it on the basis of overlap between smaller subsets.

Take the case where k = 2, since k + 1 is 3 we have {horse1, horse2, horse3} and we could argue that if we have already
proven the case where n = 2 then the two subsets {horse1, horse2} and {horse2, horse3} are the same color because
they are sets of size 2 which contain horses of the same color.

However now let k = 1, since k + 1 is 2 we have {horse1, horse2} the subsets chosen by the inductive step are
{horse1} and {horse2} these do not overlap so we cannot conclude that the horses are the same color. The fact that
the size 1 sets are the same color as themselves is not enough.

So my revised answer is that the inductive step does not work for k = 1 to get us from the case n = 1 to n = 2.
(In other words we cannot jump from saying that every horse is the same color as itself to saying that any pair of
horses are the same color. Obviously if we did find that every pair of horses were the same color, then all of the other
cases would follow. So yes I agree the fact that a set of size k + 1 is taken does not necessarily mean that the inductive
step does not work, and my answer in post #2 was not correct. At the time I had not read the pseudo proof carefully
and perhaps rushed my answer a bit. There are a few minor things about the alleged proof which are not very good style.)

 

#6 2013-05-02 21:55:27

bob bundy
Moderator

Offline

Re: Colored Horses

hi Agnishom,

I just don't think the induction step proves anything.  The k=1 case is fine.

Why not?  Well if you have a set of n similarly coloured horses, the induction step requires that you show that adding another horse gives n + 1 similarly coloured horses.  Clearly this does not happen.

Here's a contrasting example which I believe is valid.

Supposing a child has a large collection of red bricks.

The child might form the following hypothesis:

In any set of n bricks from my collection, all will have the same colour.

Proof by induction:

(i) Make a set of one one brick.  Is it the same as all the other bricks in the set.  Yes, because it is the only one.

(ii) Assume I have  a set of n bricks, all having the same colour. 
I add one more brick to the set. 
The first n bricks were all red, because of the axiom "    a child has a large collection of red bricks."
The new brick is red, because of the axiom " a child has a large collection of red bricks."

Therefore all n+1 bricks are red => the set of n+1 bricks are all of the same colour.

Proof complete.  smile

Now can someone explain a much bigger puzzle?  Why did I bother with this proof?

smile

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
 

#7 2013-05-02 22:38:52

Nehushtan
Power Member

Offline

Re: Colored Horses

The flaw in the argument is that the inductive step assumes n ≥ 2. In order to remove one horse from a set of n horses and still have at least one horse left over*, you clearly must have n ≥ 2.

You have shown that the statement S is true for n = 1. You have not shown that it’s true for n = 2. In order for the inductive proof to work, you must show that S is true for n = 2 as well – which you can’t because S isn’t true for n = 2.


*The inductive argument compares the colour of Horse #1 and of Horse #k+1 with the colour of the intermediate horses #2, …, #k. The inductive proof assumes that there is at least one intermediate horse.

Last edited by Nehushtan (2013-05-03 02:34:00)


134 books currently added on Goodreads
 

#8 2013-05-02 22:45:33

anonimnystefy
Real Member

Online

Re: Colored Horses

bob bundy wrote:

hi Agnishom,

I just don't think the induction step proves anything.  The k=1 case is fine.

Why not?  Well if you have a set of n similarly coloured horses, the induction step requires that you show that adding another horse gives n + 1 similarly coloured horses.  Clearly this does not happen.

Here's a contrasting example which I believe is valid.

Supposing a child has a large collection of red bricks.

The child might form the following hypothesis:

In any set of n bricks from my collection, all will have the same colour.

Proof by induction:

(i) Make a set of one one brick.  Is it the same as all the other bricks in the set.  Yes, because it is the only one.

(ii) Assume I have  a set of n bricks, all having the same colour. 
I add one more brick to the set. 
The first n bricks were all red, because of the axiom "    a child has a large collection of red bricks."
The new brick is red, because of the axiom " a child has a large collection of red bricks."

Therefore all n+1 bricks are red => the set of n+1 bricks are all of the same colour.

Proof complete.  smile

Now can someone explain a much bigger puzzle?  Why did I bother with this proof?

smile

Bob

Hi Bob

The statement is that every n horses are if the same colour, not a particular set of n horses.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 

#9 2013-05-02 23:25:09

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Colored Horses

I like SteveB's disproof in #5. Thanks to Nehushtan

Bob Bundy, I am not getting your point. My induction step shows that adding 1 preserves the property.

Last edited by Agnishom (2013-05-03 00:39:28)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#10 2013-05-03 05:48:00

SteveB
Power Member

Offline

Re: Colored Horses

Agnishom wrote:

I like SteveB's disproof in #5. Thanks to Nehushtan
Bob Bundy, I am not getting your point. My induction step shows that adding 1 preserves the property.

Thanks Nehushtan, that was a much clearer explanation than mine. Basically it amounted to the same thing that the
case where k=1 does not allow the inductive step to work, because an intermediate horse is needed otherwise we
end up with two equations without a horse color on the other side of the equation, because if the set only has two
horses in it then removing one leaves just one, and of course the equation needs something on both sides, and
the horses from 2 to k are non-existent.

About the Bob Bundy point: anonimnystefy has answered this already, in that Bob has (perhaps like me in my first
post) not read the theorem very well and has interpreted it in a way where the set under consideration is just a
particular set (which could be thought of as being added to by one element each time one is added to n) rather than
ANY set of that size picked from the set of all horses. I realised after studying the question more closely and thinking
about it for longer, that it could not possibly be this problem that was being intended by the author of the book.
If it were that problem then it would be the inductive step that fails and in every case it would fail because if we are
adding a new horse from an outside source from which the theorem is not anything to do with. However this is as
I mentioned earlier not a correct interpretation of the problem, and as far as I know, does not lead to anything particularly
remarkable. It does however show that human error can occur both in producing a new mathematical idea, as well
as spotting the correct flaw (as I managed to get wrong in my post #2 when I jumped to the wrong conclusion regarding
the flaw). Also communicating the idea well can cause problems as I managed to show in my next post on when I had
realised what the flaw was in my head, but did not explain it very well.

To go back to the original problem though: The inductive step does work for k = 2 and all k > 2 as well.
However if we cannot get from case n=1 to case n=2 using the inductive step (which we can't) then this does not make any
difference because the case where n=3 can only be proven by induction if the n=2 case is proven.
The case n=2 really should be proven as a separate case (another basis case), but common sense tells us
that we cannot literally go through an infinite number of horses to show this for every horse set of size 2.
In mathematics a property of the mathematics might give us some way of proving something for an infinite set,
but obviously equal horse color is not likely to have such a property. If it were a real maths problem that we were trying
to solve and the inductive step was not valid for k=1 (but was for k>1) then we would try to solve this case as a special
case unless of course there was some other way round the problem.

 

#11 2013-05-04 04:17:31

Mrwhy
Full Member

Offline

Re: Colored Horses

This reminds me of the prisoner who was told
"You will be executed one day this week but NOT if you tell us which day it will be"
So he says (like your k and k+1)
"Well I WIIL be executed one day this week
Today is Sunday, so that means BEFORE next Saturday
So if they leave it til Saturday, that is too late - for early Saturday morn I will KNOW it is "today" and they will not do it if I KNOW the day!
Similarly they cannot do it on Friday
Similarly Thursday
So they CANNOT DO It

But Wednesday the jailer knocks on the door and says "It's today and you did not tell me!"

 

#12 2013-05-04 13:20:59

Agnishom
Real Member
Award: Wink Sherlock

Offline

Re: Colored Horses

But the jailer was already told that it will be a day this week


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
'Who are you to judge everything?' -Alokananda
 

#13 2013-05-04 17:04:59

bob bundy
Moderator

Offline

Re: Colored Horses

Mrwhy wrote:

This reminds me of the prisoner who was told
"You will be executed one day this week but NOT if you tell us which day it will be"

That sounds a lot like this one:

http://www.mathisfunforum.com/viewtopic.php?id=17556

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
 

#14 2013-05-04 17:33:56

anonimnystefy
Real Member

Online

Re: Colored Horses

Ah, I remember that one.


The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
 

Board footer

Powered by FluxBB