作者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/cn.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