培玉 · 一试
一试训练题
F2填空题组合计数综合
集合1,2,4的所有非空子集的元素和去重后，分成若干组，要求每组最大值与最小值之比严格小于2。至少需要几组？
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
用倍增数给下界，再按倍增区间构造分组。
解答
所有子集和恰为1到7。1、2、4两两的比至少2，不能进入同一组，所以至少3组。分为1、2,3、4,5,6,7，每组比值均严格小于2，恰用3组。 所求为 。
复核
比值要求严格小于2，因此1与2不能同组。
方法总结
用倍增数给下界，再按倍增区间构造分组。
为什么评为 F2（会透露解法方向）
用倍增数给下界，再按倍增区间构造分组。
已记下，谢谢！