Question

离散数学， 题太难了不会解，求助！！！！！

证明：如果S是{1，2，3......n}的子集，而且S的元素个数大于(n+1)/2, 那么S一定包含两个不同的数字a和b，并且a可以整除b。

Answer 1

你好！
证明：将S中元素一一配对：
{1,2，4,8，……}{3,6,12，……}{5,10,20，……}
这样配对，直到每个奇数都配入某一对。这样的对共有[(n+1)/2]个，其中[x]表示不超过x的最大整数
如果两个数属于同一对，则必有一个整除另一个。
因为S的元素个数大于(n+1)/2，所以至少有[(n+1)/2]+1个元素
由抽屉原理，必有两个元素属于同一对。
所以S一定包含两个不同的数字a和b，并且a可以整除b。
证毕！
不明白请追问，有帮助请采纳！