每日一题2009/3/20_最大乘积是多少？

xiaoee posted @ 2009年3月20日 07:11 in Mathematics with tags 数论每日一题最值 , 3666 阅读

找出若干个正整数n1,n2,n3,...nk，使满足n1+n2+n3+...+nk=100,并且它们的乘积要是最大的？

解答：假设我们已经有了一个对100的分割并且它们的乘积是最大的，显然这个分割中不能包含1,因为我们可以去掉1,并在其它任一项上加1则得到的乘积更大。分割中也不能包含大于4的偶数k，因为我们可以用k/2和k/2去代替，由于k>4,k^2>4k,这样(k/2)*(k/2)>k,这样得到乘积更大的分割。同样，分割中不能包含大于4的奇数k，我们可以用(k-1)/2和(k+1)/2代替它，由于k>=5，可以得到k^2>=5k>4k+1,于是((k-1)/2)*((k+1)/2)>k,乘积变得更大了。这样一来分割中只含有2,3和4。而分割中不能包含1个以上的4，因为两个4可以被3,3,2代替得到更大的乘积(3*3*2>4*4)。分割中也不能含有2个以上的2,因为3个2可以被两个3代替得到更大的乘积(3*3>2*2*2)。最后分割中还不能同时含有4和2,因为它们可以被两个3代替得到更大的乘积(3*3>4*2)。结果分割中只能3,一个4或者最多两个2,考虑到和为100,就只能分成32个3和1个4（或者2个2）。