作者AirComm (AirComm)
看板Grad-ProbAsk
標題[理工] 離散 鴿籠原理 a
時間Sun Dec 15 17:18:56 2019
http://i.imgur.com/Yh0f34a.jpg
請問課本3-42的a小題 該怎麼證明呢
-----
Sent from JPTT on my Xiaomi Redmi Note 7.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.204.201 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1576401538.A.12B.html
2F：推 mistel: 把2分解出來後用奇數當籠子 12/15 17:34
3F：→ zuchang: 我的想法是1的倍數當集合，2的倍數當集合 100的倍數 則 12/15 17:44
4F：→ zuchang: 取101個數必有2數在同一集合裡 mi大的也不錯xd 12/15 17:44
5F：→ zuchang: *一直到100 12/15 17:45
6F：推 ok8752665: 可是你這樣取100~200間會有一些質數取不到喔 12/15 17:49
7F：→ ok8752665: 還是你把質數全丟到1的倍數 12/15 17:51
8F：→ ok8752665: 不過一般鴿籠不都是互斥集合嗎 12/15 17:53
9F：→ ok8752665: 這樣也不行啊 質數全丟到1的倍數 隨便取有可能不能整除 12/15 17:57
10F：推 pyramidinc: 質數就自己一個集合 集合數小於100 取101個一定會有兩 12/15 18:31
11F：→ pyramidinc: 個在同一集合裡 這樣不行嗎？ 只是不知道集合數要怎麼 12/15 18:31
12F：→ pyramidinc: 證明小於100？ 12/15 18:31
13F：→ ok8752665: 質數丟到一個集合 那你取到31 37 不就不能整除了 12/15 18:34
14F：推 pyramidinc: 總共取101個數啊 XD 只要101個數中有其中兩個可以互相 12/15 18:36
15F：→ pyramidinc: 整除就好了 不用兩兩都互相整除吧？ 12/15 18:36
16F：→ ok8752665: 取101個一定會互相整除沒錯 那是推出來的結論 但證明 12/15 18:39
17F：推 pyramidinc: 我不太懂你的意思 12/15 18:41
18F：→ ok8752665: 方面有問題啊 如果要以倍數分組的話 質數不能放一組阿 12/15 18:41
19F：→ ok8752665: 質數放一組的問題就在 你會說一定有人在同一集合 但 12/15 18:43
20F：→ ok8752665: 質數那組就不能整除彼此 12/15 18:43
21F：推 mi981027: mi大的應該就是標準解法了 用倍數分組會有o大說的 12/15 18:44
22F：→ mi981027: 子集合不互斥的問題 比如6要放在2還是3的倍數 12/15 18:44
23F：推 pyramidinc: 哦哦 我不是說所有質數放同一組 我是說各個質數自己一 12/15 18:45
24F：→ pyramidinc: 組 那只要能夠證明組合數小於100 那取101個數一定會有 12/15 18:45
25F：→ pyramidinc: 至少兩個在同一組 我的想法是這樣 只是我不知道怎麼證 12/15 18:45
26F：→ pyramidinc: 明這樣的分配方式組合數會小於100 12/15 18:45
27F：→ pyramidinc: 那就6可以放到 2或3 其中一個 只是要這樣子的分配方法 12/15 18:47
28F：→ pyramidinc: 可以讓組合數小於100 ？ 12/15 18:47
29F：→ mi981027: 那一個由多個質數相乘得到的組合數 該放在哪組 12/15 18:47
30F：→ pyramidinc: 就其中一個質數的那組 12/15 18:47
31F：推 ok8752665: 那你這樣的問題就是太難分了 我不會 0.0 12/15 18:48
32F：→ pyramidinc: 對 就是不知道要怎麼證明組合數會小於100 12/15 18:49
33F：→ ok8752665: 組合數 那2還要自己一組嗎 12/15 18:49
34F：→ mi981027: 還是不行 假設有100個質數好了 這時取101個數 12/15 18:52
35F：→ mi981027: 會有一個質數重複取到 假設重複取到的質數是3 12/15 18:52
36F：→ mi981027: 從這裡面選出來的 一個是2*3*5，一個是3*5*7 12/15 18:52
37F：→ mi981027: 這兩個數就不能相除 12/15 18:52
38F：→ pyramidinc: 2就跟所有2的倍數同一組 ？ 反正只是要同一組之間可以 12/15 18:52
39F：→ pyramidinc: 整除 然後又可以證明組合數小於100 應該就滿足鴿籠了 12/15 18:52
40F：→ pyramidinc: 吧？ 這樣分可以保證同一組的整除 但是不知道怎麼證明 12/15 18:52
41F：→ pyramidinc: 組合數小於100 12/15 18:52
42F：推 pyramidinc: 如果是有100個質數的話 那這樣的分法組合數就會大於10 12/15 18:55
43F：→ pyramidinc: 0了 所以現在就是不知道怎麼證明這樣的分法組合數會小 12/15 18:55
44F：→ pyramidinc: 於100 12/15 18:55
45F：推 ok8752665: 那這樣如何 2的倍數全放一組 3 9 27 81一組 5 25 125 12/15 18:59
46F：→ ok8752665: 一組 剩下都自己一組 保證小於100組 讚 12/15 19:00
47F：→ ok8752665: 不對 2的倍數同一組也有問題 4 跟 6又不整除 12/15 19:01
48F：→ ok8752665: 放棄 感覺就用第一個方法就好 12/15 19:01
49F：推 mistel: 關鍵在分到同一組可能不能整除 啊不過這題小黃筆記上就有 12/15 19:03
50F：→ mistel: 啦 12/15 19:03
51F：→ pyramidinc: 哦 樓上講到我沒想到的問題點了 XD 那就不能2的倍數同 12/15 19:05
52F：→ pyramidinc: 一組 還要再分組 12/15 19:05
53F：推 mi981027: 我懂p大意思 在200內的數最多只會由3個質數相乘 12/15 19:05
54F：→ mi981027: （四個質數相乘最小數是2*3*5*7 = 210 超過了） 12/15 19:05
55F：→ mi981027: 把這個組合數找出來同樣能證明 但問題就是沒跑程式的話 12/15 19:05
56F：→ mi981027: 根本不知道1~200的質數有誰 也無從分組 12/15 19:05
57F：→ mi981027: 所以乖乖用小黃的解法吧XD 12/15 19:06
58F：→ pyramidinc: 反正看到鴿籠就是想辦法怎麼分組XD 12/15 19:06
59F：推 gash55025502: 想問一下一樓大大的寫法 是任何數都可以寫成2^k*qi 12/15 19:49
60F：→ gash55025502: 的形式嗎？然後組合數是什麼意思QQ 12/15 19:49
61F：推 mathtsai: 整數為1~2n 則取n+1,n+2,...,2n則沒有任意整數互相整除 12/15 20:14
62F：→ mathtsai: 從1~n多取一個 一定會有一個整除剛才取出來的n個數字 12/15 20:16
63F：推 ok8752665: 組合數那句應該刪掉 怪怪的 沒啥意義 12/15 20:36
64F：→ ok8752665: 數字一般分質數跟合成數 12/15 20:38
65F：→ ok8752665: 改成奇數就好 阿每個數都可以表達成那個形式沒錯 12/15 20:44
66F：→ ok8752665: 每個數字質因數分解後 把2全提出放左邊 其他就是那個q 12/15 20:45
67F：→ ok8752665: 應該說質因數分解後 2的次方就是k 其他乘起來就是q 12/15 20:47
68F：→ a016258: b 小題不就提示了 a 小題了嗎? 12/15 21:06
69F：→ mathtsai: b和a肯定不會同時出現啊XDD 12/15 21:31
70F：→ Ricestone: 任意取101個，跟自己取100個再加1個不一樣啊 12/15 21:36
71F：→ Ricestone: 從1~n多取一個，那我取1不就好了 12/15 21:36
72F：推 mistel: 對耶 寫組合數真的有問題 12/15 22:01
73F：→ mistel: 不好意思（跪 12/15 22:01
74F：推 gash55025502: 感謝ok大解釋 看懂了！！ 12/16 15:21