JK弟弟 發問時間: 科學數學 · 1 0 年前

幫忙解答 離散數學的題目

小明想用數學歸納法證明「對任意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個人全部都在同一天出生,

根據數學歸納法得證。

請問:小明錯在哪兒呢?

5 個解答

評分
  • Leslie
    Lv 7
    1 0 年前
    最佳解答

    小明的 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_sa...

    錯的原因就是不該把 n = 1 當為basis.

    應該是 n = 2. 或是, 應該像我做的,

    把 n=1 及 n=2 都當 basis, 然後發現 basis 是不成立的.

    參考資料: 小明的老師
  • 1 0 年前

    推"失去羽翼的羊"大大的簡潔有力

    跟我要說的一樣

    其原因是要說每個個體都獨立的關係

    沒辦法推"+1"的東西

  • prime
    Lv 4
    1 0 年前

    這個歸納法錯在當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 補充:

    你舉的例子剛好說明這個例子錯在哪...

    上面英文的說明跟我說的理由一樣

    請你去弄懂歸納法說什麼再說.

  • YO
    Lv 5
    1 0 年前

    n=2不成立

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

    所以起點要考慮n≥2吧

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

  • 您覺得這個回答如何?您可以登入為回答投票。
  • 1 0 年前

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

還有問題?馬上發問,尋求解答。