小米
Lv 5
小米 發問時間: 科學數學 · 6 年前

以Pigeonhole principle解一充分必要條件

 

有請數學達人們幫忙解一充分必要條件數學題

底下有兩例題

請以Pigeon Principle原理解釋

看了國外網站的解釋

看了好久仍然不懂 

 

(題一) 

在13張卡片上,每張卡片各寫上4個英文單字,若每張卡片必有一英文單字,與其餘剩下的12張卡片之中,4個英文單字的其中一個相同,且只能有一個相同,(若且唯若),兩兩卡片,不能有兩個單字以上相同,且不能有單字均不相同的情況。試問:最少要有多少單字才能滿足這13張卡片?

 

(題二) 是一模一樣題型,只是想更清楚比較原理

如上題

若卡片數量改為55張,每張卡片上面有8個英文單字。試問:最少要有多少單字才能滿足這55張卡片?

 

百思不得其解

有請數學達人們幫忙解惑

 

感謝!

 

感謝專家達人了!

 

已更新項目:

 

(題二)

 

國外網站上

數學達人的解釋是

 

55張卡片

每張卡片8個單字

以Pigeonhole Principle原理來看

55張卡片中每張卡片的7個單字都要不同

也就是pigeonhole有七個

第8隻pigeon就一定會是重複的

所以解答為8+7*7=57種

 

上面解釋基本都懂

最後一句話解釋得太快

就是卡在這裡不懂

 

有請達人們了

 

感激不盡

 

1 個解答

評分
  • 6 年前
    最佳解答

    由小做起,若只可寫上3個字。為方便解說,將這3個字分兩組,一組全英文字母,一組全數字。全英文字母的有3個:A, B, C所以只用全部英文字母的有一種;另外的卡片只能是一個英文字母加2個數字,所以數字共有 2x2 個。組合有:1+3x2=1+2+2x2=3+2x2 (等同書上的公式)即 7 個單字總共可以有 7 張卡片:ABC, A12, A34, B13, B24, C14, C23

    若可寫上4個字的。

    將這4個字分兩組,一組全英文字母,一組全數字。

    全英文字母的有4個:A, B, C, D

    所以只用全部英文字母的有一種;

    另外的只能是一個英文字母加3個數字,所以數字共有 3x3 個。

    組合有:1+4x3=1+3+3x3=4+3x3 (等同書上的公式)

    即 13 個單字總共可以有 13 張卡片:

    ABCD, A123, A456,A789, B147, B258, B369, C159, C267, C348, D168, D249, D357

    (題一) 所以最少要有 13 個單字才能滿足這13張卡片。

    ⋯⋯⋯⋯

    若可寫上8個字的。將這8個字分兩組,一組全英文字母,一組全數字。全英文字母的有8個,所以只用全部英文字母的有一種;另外的只能是一個英文字母加7個數字,所以數字共有 7x7 個。組合有:1+8x7=1+7+7x7=8+7x7 (等同書上寫的)即 57 個單字總共可以有 57 張卡片。(題二) 所以最少要有 57 個單字才能滿足這55張卡片。

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