[理工] 離散 鴿籠原理 a

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