从1~120这120个正整数中取出n个数,使得没有一个数是另一个数的2倍,则n的最大值是多少?
解答是80
想了很久但想不到该怎么下手,还请各位大大帮帮我,感谢!
先考虑后半段61-120,再来考虑这些前面1-60乘上两倍不会在61-120里面,全部最多有1-30的奇数,
最后还有一些偶数在1-30里面,这些偶数有个特性就是乘上两倍不为1-30的奇数的两倍,两倍后数也可以在31-60里面.
首先616365....119这30个不为别数两倍也不会被别数两倍的数一定要全选少选一个就损失一个.
接下来626466....120这30个可以考虑全选因为例如少选一个64则只可多选一个32但16又不能选了.
最后选135...29有15个以及481216202428这7个中最多只能挑5个如412162028.
因此n最多30+30+15+5=80
本以为从1~3m这3m个正整数中取出n个数,使得没有一个数是另一个数的2倍,则n的最大值是2m
本题有两个方式可以进行而且重点是要说明为何能是最多个数的取法.
1.由小而大能取就取的取法(此为总和最小的取法) :
一个30可以选故A可以保证是最多个数的取法.
如此我们选出(120119...61)(3029...16)(7654)(1)共60+15+4+1总共有80 个数是最多个数的取法.