Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Fallacious proof/all horses are the same color"
(header)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for <math>n = 2</math>), the fact that all horses have the same color would follow.  Unfortunately, the case <math>n = 2</math> does not follow from the case <math>n = 1</math>. The first horse is the same color as itself, and so is the second horse, but there is no overlap.
+
== All horses are the same color==
  
−
{{stub}}
+
We shall prove that all horses are the same color by induction on the number of horses.
 +
 
 +
First we shall show our base case, that all horses in a group of 1 horse have the same color, to be true. Of course, there's only 1 horse in the group so certainly our base case holds.
 +
 
 +
Now assume that all the horses in any group of <math>k</math> horses are the same color. This is our inductive assumption.
 +
 
 +
Using our inductive assumption, we will now show that all horses in a group of <math>k+1</math> horses have the same color. Number the horses 1 through <math>k+1</math>. Horses 1 through <math>k</math> must be the same color as must horses 2 through <math>k+1</math>. It follows that all of the horses are the same color.
 +
 
 +
===Explanation===
 +
 
 +
Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for <math>n = 2</math>), the fact that all horses have the same color would follow.  Unfortunately, the case <math>n = 2</math> does not follow from the case <math>n = 1</math>. The first horse is the same color as itself, and so is the second horse, but there is no overlap and so we cannot deduce that the two horses are the same color.
 +
 
 +
[[Fallacious proof | Back to main article]]

Latest revision as of 20:22, 2 November 2007

All horses are the same color

We shall prove that all horses are the same color by induction on the number of horses.

First we shall show our base case, that all horses in a group of 1 horse have the same color, to be true. Of course, there's only 1 horse in the group so certainly our base case holds.

Now assume that all the horses in any group of $k$ horses are the same color. This is our inductive assumption.

Using our inductive assumption, we will now show that all horses in a group of $k+1$ horses have the same color. Number the horses 1 through $k+1$. Horses 1 through $k$ must be the same color as must horses 2 through $k+1$. It follows that all of the horses are the same color.

Explanation

Our base case is not the appropriate base case: if one could show that every pair of horses has the same color (the result for $n = 2$), the fact that all horses have the same color would follow. Unfortunately, the case $n = 2$ does not follow from the case $n = 1$. The first horse is the same color as itself, and so is the second horse, but there is no overlap and so we cannot deduce that the two horses are the same color.

Back to main article

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Fallacious_proof/all_horses_are_the_same_color&oldid=19102"