轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 问题求解，第一个答对的有奖 [打印本页]

作者: 青石 时间: 2005-1-2 01:28

证明：如果从1，2，3……，199，200中选出100个整数，所选的这些整数中有一个小于16，那么存在2个所选的整数，使得它们中的一个能被另一个整除。

对于第一个完整给出证明的人，我以500通宝答谢！

作者: loranrowe 时间: 2005-1-4 23:17

嗯嗯，俺也有一个
sign
顶一下先

提供一个思路
15^2=255>200>14^2=196
猜测
存在自然数m,n，m^2>2n>m-1^2
对于[1，2n],任取n个数a1,a2,...,an
若其中存在某个ai<=m
则a1..an中存在两个数，其中一个是另一个的倍数
归纳证明之

作者: 青石 时间: 2005-1-5 01:25

这个题要用抽屉原理

但是我不知道怎么构造抽屉

困扰一年多了

还是做不出来

作者: 瓦灰 时间: 2005-1-5 16:15

以前下了篇文章,上面恰好有这道题,后半部分用到了反证法(不容易想到啊),不过不是我做出来的,拿出来大家分享.

附件: 新建写字板文档.doc (2005-1-5 16:15, 19.75 K) / 该附件被下载次数 364
http://xycq.org.cn/forum/attachment.php?aid=3980

作者: 重阳 时间: 2005-1-5 17:20

晕啊，刚写下了一个证明。不管了，辛辛苦苦写出来的东西，不能让他死在机器里。

用抽屉法则结合反证法是第一感，

首先把101至200各放于一个抽屉；
第二步，在偶数N所在的抽屉中加入数字N/2；
第三步，若上一步计算的N/2仍是偶数，加入数字N/4；
重复第三步，加入N/8，N/16等，直至最后得出一个奇数。
抽屉构造完毕，显然从101至199的所有奇数独占一个抽屉。

对数列M，2M，4M，8M，16M……（M为1至100的整数），易知其中有且仅有一个数字在101至200之间，因此上述的抽屉中包含了1至100的所有数字且不重复。

从任一抽屉内任取2个数（假如有2个或更多数字的话），用小数去除大数，必能整除。因此假如存在100个数相互不能整除的话，必定是从这100个抽屉中各取一数。下面证明在有一数A小于16的情况下这是不可能的。

1、任何小于67的奇数A都不可能在所取的100个数之中。
因为从101至199的奇数中至少有一个是它的倍数。从35到65，有3A；从21到39，有5A；从15到27，有7A（下略）。
2、所有小于46的4N+2型偶数A也不可能在所取的100个数之中。
在3A所的在抽屉中，除3A/2之外，所有其它数都是A的倍数，若A在100个数之中，3A/2也必在其中，而3A/2是个小于67的奇数，由（1）知这是不可能的。
3、所有小于30的8N+4型偶数A也不可能在所取的100个数之中。
在3A所在的抽屉中。除3A/2、3A/4之外，所有其它数都是A的倍数。若A在100个数之中，则3A/2、3A/4两数中必取一个。而3A/4是小于67的奇数，3A/2是小于46的4N+2型偶数，由（1）（2）知这是不可能的。
4、所有小于20的16N+8型偶数A也不可能在所取的100个数之中。
在3A所在的抽屉中。除3A/2、3A/4、3A/8之外，所有其它数都是A的倍数。若A在100个数之中，则3A/2、3A/4、3A/8三数中必取一个。而3A/8是小于67的奇数，3A/4是小于46的4N+2型偶数，3A/2是小于30的8N+4型偶数，由（1）（2）（3）知这是不可能的。

以上四类数，已经包括了小于16的所有数。命题得证。

作者: 青石 时间: 2005-1-5 17:28

明白了

非常感谢瓦灰
以500通宝答谢

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)