鴿籠原理之應用

將 1 至 100 分成 50 組, 每組都是兩個互質的數字 :
(1, 2), (3, 4), (5, 6), ..., (99, 100).
所以, 從中取出 51 個數, 必定有兩個數互質的.

(最壞的情況是你連續取 50個雙數, 但第 51個一定是單數, 它一定同 2 互質的.)


2012-06-06 10:44:51 補充：
安哥大大, 當然可以有不均分的分法, 只要是互質的就可以同一組. 如 :
第一組是所有質數, 即 (2, 3, 5, 7, 11, 13, ...)
第二組是 (1, 4, 9, 25, 49)
第三組是 (6, 27)
...
可以見到每組都只有一個雙數. 所以有 50 組.
取出51個數, 必定可從中取出互質的兩數.

2012-06-06 10:56:59 補充：
最壞的情況就是你連續取50個雙數, 都沒有兩個數是互質的. 但當你取第51個時, 你會發現第51個會同某一個雙數是在同一組的. (上面列出的50組)

"最壞的情況是你連續取 50個雙數"
1-100 就50個雙數(偶數), 第51個數字又
怎會是偶數, 那50個雙數中又怎會沒有2?

謝謝Copestone的意見，但是你為何不直接回答呢？我可以選你為最佳解答。

2012-05-31 16:29:15 補充：
我想了解一下，是否有其他的分類法？因為我同時還問了另外一題(詳見"鴿籠原理之應用(2)")，回答者也是分成50組，但不是每組都兩個數字，所以我懷疑有不均分的方法。

To 001 意見：

你 51 個數字中是一定有偶數及奇數，但是不一定有 2 啊。

＝＝＝
其實，只要取相鄰的數字組即可：

把 1 到 100 分成 50 組：{1, 2}, {3, 4}, {5, 6}, ..., {99, 100}。〔籠子〕

由鴿籠原理，抽出的 51 個數字〔鴒子〕放進對應的組中，必有一組〔個籠子〕含兩個數字〔兩隻鴒子〕，這兩個數字必為互質。

2012-05-31 05:07:42 補充：
呵，他好像想說，有一種情形，抽取了全部的偶數，而剩下的一個一定是奇數，因為所有偶數都在了，斤以有 2, 而 2 與那個奇數互質。

不過，舉這個特例無多大意義，而且怎樣的最壞法？令人莫名奇妙。