Author |
Topic: Easy: All horses same color (Read 571 times) |
|
Felix
Newbie
Gender: 
Posts: 1
|
 |
Easy: All horses same color
« on: Mar 19th, 2005, 11:08am » |
 Quote  Modify
|
Theorem: All horses are the same color.
Base Case: 1 horse. Clearly with just 1 horse, all horses have the same color.
Inductive Step: If it is true for any group of N horses that all have the same color, then it is true for any group of N+1 horses. Given any set of N+1 horses, if you exclude a random horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding any other horse in the pack of N+1 horses, you can conclude that the last N horses also have the same color. Therefore all N+1 horses have the same color. QED.
Well this is a very good one, and the trick is really subtle.
The trick ISN'T, as I first thought, the base case. It's obviously right: all horses in the group of one horse are of the same color.
The real trick is in the inductive step. You have N+1 horses. If you exclude one, you have N horses left, of the same color A. If you exclude another, you have N OTHER horses of the same color B. But why on earth would A and B be the same color??
They would if one horse would be in both N horses groups. But that's only true if N>=2 ... Hence the trick.
(Sorry if I'm not clear enough, but english is not my native language)
|
|
 IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Easy: All horses same color
« Reply #1 on: Mar 19th, 2005, 12:01pm » |
Quote Modify
|
The logic in the proof is actually totally sound in every case except N=2. The problem with the N=2 case is that just because every 1-horse subset consists entirely of horses of the same color we cannot conclude that the set of two horses consists entirely of horses of the same color.
By contrast, in the N=3 case everything is OK, since by transitivity it always suffices to show that every 2-horse subset of a given set of horses consists entirely of horses of the same color.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print