錯在哪裏？定理：所有的房子的顏色都是一樣的。

Theorem. All horses are the same color.

Proof. We'll induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color.

Now, for the inductive step: we'll show that 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.

Well, given any set of N+1 horses, if you exclude the last horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding the first 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.

Hmmn... clearly not all horses have the same color. So what's wrong with this proof by induction?

所有跟帖： 

• 先找出一條明顯的錯 -布衣之才- ♂ (31 bytes) () 08/22/2012 postreply 19:01:27

• haha...You are absolutely right. -wxcfan123- ♂ (0 bytes) () 08/22/2012 postreply 19:42:17

• 沒什麽,用等價的概念就過去了.搞數學的,是粗心的細心人. -jinjing- ♀ (0 bytes) () 08/23/2012 postreply 05:25:21

• 同色是比較概念,至少兩個馬.從2開始,如對,可推出所有馬同色. -jinjing- ♀ (0 bytes) () 08/22/2012 postreply 19:30:47

• 當然，任意兩匹馬同色等價於所有的馬同色。問題是上麵的證明錯在哪？ -wxcfan123- ♂ (0 bytes) () 08/23/2012 postreply 18:01:21

• 錯在同色的定義.一匹馬同色,與其它馬無關,這過程證明了每匹馬與自己同色. -jinjing- ♀ (0 bytes) () 08/23/2012 postreply 20:00:24

• Real Math is here: f(hi1,i2,...,hit)=b,meaning t horses have b c -jinjing- ♀ (148 bytes) () 08/24/2012 postreply 12:02:25

• 說說我的看法。這裏的歸納推理的第二步有三個集合 -wxcfan123- ♂ (248 bytes) () 08/24/2012 postreply 18:01:09

• 謬在第二步。 -cantorian- ♀ (201 bytes) () 08/25/2012 postreply 18:57:23

• 這些集合並沒有問題，它們是N+1匹馬的兩個子集。 -wxcfan123- ♂ (0 bytes) () 08/25/2012 postreply 20:41:07

• 這兩個子集不是題目裏的集。 -cantorian- ♀ (142 bytes) () 08/25/2012 postreply 22:19:22

• 有趣 -發獎- ♂ (397 bytes) () 09/12/2012 postreply 16:36:43