兩個題目

[曾阿牛 10]

這裡放上兩個看起來類似的題目

請說明以下兩個敘述為真：

1. 從1到100的正整數中任選51個　必然選中兩個數字　其中一個是另一個的因數

(如果看不懂題目的話　這裡有比較詳細的說明：　

從1到100的正整數中任選51個　在你選的51個數字中　必定存在兩個數字　這兩個數字小的那一個是大的那一個的因數)

2. 從1到100的正整數中任選51個　必然選中兩個彼此互質的數字

PS. 我不是來求助的　所以　慢慢想沒關係　

我只是想看看這兩題放在一起時　各位的作法會是如何

[司馬特 12]

第二題

"必然選中兩個彼此互質的數字"

那就故意挑選不互質的數字,也就是51個數字都有共同的因數:

先從2開始,選取所有偶數:2 4 6 8 10 ......96 98 100,共50個,剩下1個至少會和2互質.

改從3開始:3 6 9 12 15 18 21......93 96 99,共33個,接下來的18個至少都和3互質.

以此類推可以得知"從1到100的正整數中任選51個,必然選中兩個彼此互質的數字"

[司馬特 12]

第一題

"兩個數字小的那一個是大的那一個的因數"

那就不要挑選選過數字的因數:

先從100開始:100 99 98 97 96......52 51,共50個數字,剩下任一個皆有前50個數字的因數.

我只想得到這種選法,不知道還有沒有其它選法?

[Liann 10]

第一題

在1~100中，如果選中97這種很大的質數，剩下50個數字卻又沒有選到1的話，就沒有其他因/倍數了。

故錯(是嗎?)

我一直以為第一題就是「公因數≠1」的意思，到最後只想出這個= ='

[悠閑 10]

1.構造集合

{1,2,4,8,16,32,64}

{3,6,12,24,48,96}

{5,10,20,40,80}

{7,14,28,56}

{9,18,36,72}

{11,22,44,88}

{13,26,52}

{15,30,60}

{17,34,68}

....

{97}

{99}

共50個集合

取51個必有兩個在同一集合(鴿籠),證畢。

另外，樓上幾位的做法基本上是極端化的情況

概念比較類似"我盡力了還是會這樣，所以我也沒法子了~"

這樣的證明在數學上是不完全的

[悠閑 10]

另外，其實我覺得或許不需要51個就可以成立了

不過構造方法我要再想想,,,,

[曾阿牛 10]

Re #6 bihubg1814

存在一種選法　能選50個數字　能讓其中任意兩個不為因數倍數的關係

您可以試著把那選法找出來　然後您就會接受　51 是最小能保證的數　或是說"需要51個"

啊... 事實上　在 #3 司馬特 的回覆裡就出現了那樣的選法

Re #5 bihubg1814

哇～　解得很漂亮　　在此　我補充一下您的構造方式

1 ～ 100 中有 50 個奇數　透過這 50 個奇數把 1 ～ 100 分成 50 個類別(也就是籠子)

任意正整數都可以(唯一)分解成一個偶數乘一個奇數　譬如說　40 ＝ 8 X 5

此時 我們就把 40 和 5 放在同一個籠子

您的這個解法雖然不難　但也沒這麼簡單　我很好奇　您是自己想的嗎？　還是說曾經見過這問題

老實說　我所查閱過有關鴿籠原理的資料　幾乎都有這一題

第二題　則比較少見　所以我丟上來考考大家

Re #4 Liann

Liann 您沒有了解題目

如果選中97　剩下50個數字卻又沒有選到1　但是這剩下的50個數可能選到 11 和 33

那就有因/倍數了

此內容已被編輯, January 30, 2012 ,由 曾阿牛
補充幾點

[悠閑 10]

Re #6 bihubg1814

存在一種選法　能選50個數字　能讓其中任意兩個不為因數倍數的關係

您可以試著把那選法找出來　然後您就會接受　51 是最小能保證的數　或是說"需要51個"

啊... 事實上　在 #3 司馬特 的回覆裡就出現了那樣的選法

噢對不起我疏漏了

看來我得多注意一點

Re #5 bihubg1814

哇～　解得很漂亮　　在此　我補充一下您的構造方式

1 ～ 100 中有 50 個奇數　透過這 50 個奇數把 1 ～ 100 分成 50 個類別(也就是籠子)

任意正整數都可以(唯一)分解成一個偶數乘一個奇數　譬如說　40 ＝ 8 X 5

此時 我們就把 40 和 5 放在同一個籠子

應該說，任何一個正整數都可以唯一分解成二的次方乘一個奇數

不然會造成一個數會在多個集合裡出現

也有可能造成在同一集合內大數不為小數倍數的可能

例如，如果只分解成一偶一奇

那12(=3x4)跟18(=3x6)可在同一集合內

但12不是18的因數。

您的這個解法雖然不難　但也沒這麼簡單　我很好奇　您是自己想的嗎？　還是說曾經見過這問題

老實說　我所查閱過有關鴿籠原理的資料　幾乎都有這一題

第二題　則比較少見　所以我丟上來考考大家

我是沒有看過，

但這是常見的手法，

凡證明"若取____個則必____"的類型，

鴿籠會是一個好方向，

但他的難就在於如何構造出恰當的集合，

這也是鴿籠概念雖簡單但卻吸引人的地方。

老實說我在構造的時候也想了一下呢....:)

[ck991021 10]

2.

反證

1不取，2不取，不然只能取50個2的倍數。更一般的，任何質數的整數次冪都不能取，因為必定悲劇。

想辦法使取的數盡量多，考慮最小數必定為兩質數相乘，因為 3x5x7=105。設為pq

每個被取的數都要是p或q的倍數，當p,q都不為2時取不到51個。設pq為2p

取的偶數中找一個數2q不是p的倍數,取的奇數中一定都是q的倍數，這樣奇數最多只有6個，偶數無法取到45個(2,4,8,16,32,64不能取)

只有形如2qr的數那就更悲劇了

[曾阿牛 10]

噢對不起我疏漏了

看來我得多注意一點

解題時　先看別人的做法　未免少些樂趣

應該說，任何一個正整數都可以唯一分解成二的次方乘一個奇數

感謝糾正 :)

老實說我在構造的時候也想了一下呢....:)

我第一次看到這題　晚上睡不著時就拿來想　斷斷續續用了三星期解

第二次看到這題　已經隔了兩三年　大約花20分鐘解

後來常教人這題　不想記也記起來了

Re #9 ck991021　悲劇？！？！　看了大大的文章　恕我愚昧　我只看懂"悲劇"

關於第二題　司馬特　在 #2 已經提供了一個解法

從司馬特的發文順序來看　他是先解出第二題

剛好跟我的經驗相反　我是先解第一題

由於我的經驗　在解第二題時　我知道這題八成要構造籠子與鴿子

但後來籠子造不出來　最後我還是選擇了用司馬特同樣的方法解題

以下　我用白色的字體寫下構造籠子的方法　讓還想自己解的人就可以看不到

想看的人將它反白就可以了

{1, 2}, {3, 4}, {5, 6}, ......, {97, 98}, {99, 100}

如此一來　問題就輕描淡寫的解決了

但我個人認為　這絕對不是個簡單的題目

希望大家有獲益;-)

[asd768999 10]

2.

如果在1~100的整數中選出51個數，那必定會有兩數是相鄰的，而這兩數就是互質的了。

應該對吧？