从1~100任意挑出51个数来 其中一定有8个数公因数大于1 谁能证明!

Question

从1~100任意挑出51个数来 其中一定有8个数公因数大于1 谁能证明!

Answer 1

100内共有25个质数,类似于埃拉托斯特尼筛法,对1~100进行分类：
第1类：1（单独拿出来,共1个）
第2类：2的倍数（2,4,6,……,100共50个）
第3类：3的倍数（3,9,15,……,99共17个）
第4类：5的倍数（5,25,35,55,65,85,95共7个）
第5类：7的倍数（7,49,77,91共4个）
第6类：11的倍数（11共1个）
……
第26类：97的倍数（97共1个）
从1~100任意挑数,假设没有8个数公因数大于1,那么最多能挑出多少个数呢?
第1类及第6~26类都只有1个数,可以全挑出来,这样挑出了22个数.
第4,5类分别只有7,4个数,没有“危险”,也可以全挑出来,这样又挑出11个数.
第2,3类分别有50,17个数,若任意一组中挑出8个数,就会使这8个数的公因数大于1,所以这两类每类最多挑出7个数,这样又挑出14个数.
由上面的分析,最多能挑出22＋11＋14＝47个数.
但题目要求任意挑出51个数,已经超过47个了,所以一定至少有8个公因数大于1,命题得证.