Ref : http://xkcd.com/617/
A Proof by Induction with a Difficulty
from gilkalai.wordpress.com
Ref : http://gilkalai.wordpress.com/2009/07/22/a-proof-by-induction-with-a-difficulty/
By Gil Kalai
Ref : http://gilkalai.wordpress.com/2009/07/22/a-proof-by-induction-with-a-difficulty/
By Gil Kalai
The time has come to prove that the number of edges in every finite tree is one less than the number of vertices (a tree is a connected graph with no cycle). The proof is by induction, but first you need a lemma.
Lemma: Every tree with at least two vertices has a leaf.
A leaf is a vertex with exactly one neighbor.
Well, you start from a vertex and move to a neighbor, and unless the neighbor is a leaf you can move from there to a different neighbor and go on. Since there are no cycles and the tree is finite you must reach a leaf. Of course you describe the argument in greater detail and it seems that everybody is happy.
Good.
Theorem: A tree 
After checking the basis for the induction we argue as follows: By the lemma 
Student: Now what about the case where 
(In square brackets what I and the students are thinking.)
Me: [I have been here before. There is no way out, just like getting to North Beacon street in Boston] You see, we proved that every tree has a vertex
Student: Yes, we proved that, but what about the case where
Me: But I can assume that
Student: You said several time that in a proof we have to check all the cases [yes, you can assume whatever you want, you are the teacher]. So what about the case where
Me: Look, I can handle the case where
Student: [At last. Now you are talking. Explain how you handle it and we can go home]
Me: It is a bit complicated.
Many students: [So this is why you did not want to deal with it from the beginning; it is complicated.]
Some students realize that I can assume that
Me: But the main point in that I do not need to deal with this case. [pray hard now]
Student: [Here you go again] Why?
Me: Because in the proof we can assume that
Student: yes, yes.
Me: (victoriously) ) So we can choose
Student (really victoriously) : And what about the case that
07/13/09 PHD comic: 'Great Tweets of Science'
from PHD Comics
Ref : http://www.phdcomics.com/comics.php?f=1198
Ref : http://www.phdcomics.com/comics.php?f=1198
| Piled Higher & Deeper by Jorge Cham | www.phdcomics.com | |
 | ||
| title: "Great Tweets of Science" - originally published 7/13/2009 For the latest news in PHD Comics, CLICK HERE! | ||
Subscribe to:
Posts (Atom)
Posts
