幫忙解答 離散數學的題目

Question

小明想用數學歸納法證明「對任意n個人而言，他們的生日一定都在同一天」，他的證明如下：
(1)Root step: 當只有一個人 (n=1時)，此敘述為真。
(2)Snowball step: 假設「對任意k個人而言，他們的生日一定都在同一天」為真，
則當有k+1個人（編號1, 2, …, k+1）時，根據假設，
第1人至第k人（共k個人）一定在同一天出生，
而且第2人至第k+1人（共k個人）也一定在同一天出生，
由此可知這k+1個人全部都在同一天出生，
根據數學歸納法得證。
請問：小明錯在哪兒呢？

Answer 1

小明的 Snowball step (即 inductive step) 基本上沒問題,
但是必須 k 要 >= 2 才行, 也就是
假設「對任意k個人 (k >= 2) 而言，他們的生日一定都在同一天」為真，
則可推到 k+1個人 時也為真. (推導過程如您所寫的)
因此, 小明的 Root step (即 basis step) 就必須是 (含兩部份):
(1.1) 當只有一個人 (n=1時)，此敘述為真, 證明:
把 "生日一定都在同一天" 也當做是有反射性的關係 (reflexsive), 因此,
自己和自己是同一天生. 成立.
(1.2) 當 n=2 時, 要證 "任兩人的生日都在同一天".
但這顯然不成立.
因此, Root step 不為真, 就算 Snowball step 正確,
合起來也無法證明原式!!

2007-10-05 12:15:01 補充：
最有名(最早)的錯誤歸納的例子是大師 Polya 的
"所有的馬都是同一顏色". 見
http://en.wikipedia.org/wiki/All_horses_are_the_same_color_%28paradox%29
錯的原因就是不該把 n = 1 當為basis.
應該是 n = 2. 或是, 應該像我做的,
把 n=1 及 n=2 都當 basis, 然後發現 basis 是不成立的.

Answer 2

推"失去羽翼的羊"大大的簡潔有力
跟我要說的一樣
其原因是要說每個個體都獨立的關係
沒辦法推"+1"的東西

Answer 3

這個歸納法錯在當n=1跳到n=2的時候
你可以看看歸納法假設, n=1時成立.
只是知道"第1人與第1人的年紀相同,第2人與第2人的年紀相同"
無法推得第1人與第2人年紀相同.
意思就是你的推論在k=1是錯的...


2007-10-05 09:58:19 補充：
意思就是你的推論在k=1是錯的.
即當n= k=1成立時,無法保證 n= k + 1 = 2 成立....

2007-10-05 10:05:45 補充：
如果歸納法是要證明對於n=1以後的數都成立,
Root Step 根本不需要證明 n = 1.
歸納法的精神就是當某數成立就可以保證當某數+1成立.
之所以有些證明會去證明n比較小的例子,是他們的証明在n比較小的部份過不去,只好分開討論!!!

2007-10-05 10:07:38 補充：
如果歸納法是要證明對於n=1以後的數都成立,
Root Step 根本不需要證明 n = 2.
歸納法的精神就是當某數成立就可以保證當某數+1成立.
之所以有些證明會去證明n比較小的例子,是他們的証明在n比較小的部份過不去,只好分開討論!!!

2007-10-05 10:09:47 補充：
你的歸納法證明,那一步要對,k最少要是3.不然你根本沒有等式可以讓全部人都相等.

2007-10-05 14:03:43 補充：
如果需要證明n=2,為什麼不需要證明n=3,n=4,n=5??

2007-10-05 14:06:52 補充：
你舉的例子剛好說明這個例子錯在哪...
上面英文的說明跟我說的理由一樣
請你去弄懂歸納法說什麼再說.

Answer 4

n=2不成立

因為命題有"同"一天這種詞的出現

所以起點要考慮n≥2吧

單一一個東西是沒有所謂"同"這種概念的

Answer 5

第 k + 1 人 不一定跟 前 k 個人生日相同