对于这个结论我们已知以下结論:
因此2与3也不需要拆分
对于4而言,因为 因此4是可以拆的(4拆与不拆是等价的)
因此我们真正需要证明的是,假设 则n可以被拆为多个2與3三个数的和大还是积大,其乘积最大
首先简化问题:假设 则n可以被拆为两个正整数三个数的和大还是积大,其乘积大于n
设函数 显然,若 则说明将n拆分为a与n-a这两个正整数的积比a大反之亦然
易求得: ,令 可解得:
,可知上述取值点为函数极大值由于只有一个极值点,因此该点为最大值
由于实际的取值a是正整数(离散的)因此我们对于偶数n和奇数n分别讨论函数最大值:
因此当n为偶数且 时,存在更优嘚拆分为两个正整数的方案(即存在两个正整数n为这两个正整数三个数的和大还是积大,且这两个正整数的积大于n)
由于 不是整数因此我们取:最大值为
令上述值>0,可解得: 因为n为正整数且 ,最终解为
因此当n为奇数且 时存在更优的拆分为两个正整数的方案
综上所述,当n为正整数且 时存在更优的拆分为两个正整数的方案
现在我们证明原问题:假设 ,则n可以被拆为多个2与3三个数的和大还是积大其乘積最大
同时我们知道 时也可拆,因此上述问题进一步归纳为:
假设 则n可以被拆为多个2与3三个数的和大还是积大,其乘积最大
对于任意的n(n符合题目假设条件)若拆分为a与b后, 则a或b是可拆的(所谓可拆就是指拆分后存在两个正整数,这两个正整数三个数的和大还是积大為该数且积大于等于该数)
因此易得:将n进行有限次拆分之后可以变成任意个正整数这任意个正整数可能含有1、2或3
但可以观察到 ,注意 為最小值因此对于任意的上述n,若拆解后其中一个数为1则拆解的两个数的积必定小于n,因此这样的拆解方案是无效的
所以上述结论归納为:将n进行有限次拆分之后可以变成任意个正整数这任意个正整数可能含有2或3,此时的乘积在所有拆解方案中必定最大
若n=2则答案为1,因为2只能被拆解为两个1
若n=3则答案为2,因为3能被拆解为1和2时比拆解为3个1更优
若n>=4则优先拆出3,直到余数小于3为止但是若余数为1,则拿絀一个3凑成4然后拆解为2+2(因为拆解为1必定不为最优上面已经讨论过)
为什么优先拆3比优先拆2更好呢?
显然此时 我们在该约束下,最大囮函数
显然 因此函数 是单调递减的,即2越少3越多乘积越大
因此,在任何情况下优先拆3都比优先拆2要好,只需要对于余数为1的情况进荇如上特殊处理即可得到最优解