小学数学题（结论简单，证明可不会）

caozhi700

一个整数（大于等于5）任意分成几个整数之和，问如何分才能使这些数的乘积最大。

醉乡常客

这个证明不是小学问题，是高中以后的问题。

bookish

先说一下如何分。根据动态规划的最优化原则，又考虑到4=2*2，所以一个整数拆成3、2、1，乘积可达到最大值，其数学表达式可写成（若有错误请指正）：

设整数为N，n=[N/3]（[x]表示x取整），N mod 3 为N除以3的余数，
若N mod 3 = 0, f(N)=power(3, n)
若N mod 3 = 1, f(N)=2*2*power(3, n-1)
若N mod 3 = 2, f(N)=2*power(3, n)

请高手给出证明f(N)具有最大值的具体步骤。

醉乡常客

bookish的证明我看不太懂。 运筹学已经放了十一年了。。


这道题应该是：x1+x2+……+xn＝N（N≥5，n≥2，n、N都是自然数）

求满足x1·x2·……·xn取最大值的x1……xn。

bookish

醉兄，我这不是证明，只是一个提示。
我给出的这个最大乘积的算法，条件可放宽到N≥2。
例如，
N=2, n=[2/3]=0, N mod 3 = 2, f(N)=2*power(3,0)=2
N=11, n=[11/3]=3, N mod 3 = 2, f(N)=2*power(3,3)=2*3*3*3=54

醉乡常客

其实这道题主要是让小孩子知道分均匀点，乘积更大。

要给出一般性的证明真的不容易。
特别是N、n都很大的时候，划分很多，一般性检验方法不好找。

我依稀记得有种笨方法是逐个比较。   

bookish

caozhi700:
　　一个大于等于5的整数任意分成几个整数之和，问如何分才能使这些数的乘积最大。

醉乡常客:
　　设x1+x2+……+xn＝N（N≥5，N和x1，x2，……，xn都是自然数），求使x1·x2·……·xn取最大值的n，x1，x2，……，xn。

解：

设
　　N = x1 + x2 + …… + xn,

　　F(N,i) 是集合 {x1·x2·……·xn; n, x1，x2，……，xn 属于自然数} 中的一个元素,
　　F(N,0) = N
　　F(N,i) = f(i) * f(N - i) (i = 1, 2, ……, N - 1)

　　f(N) = max {F(i,N)} = max {x1·x2·……·xn; n, x1，x2，……，xn 属于自然数}

即，

F(1,0) = 1 --> f(1) = 1

F(2,0) = 2
F(2,1) = f(1)*f(1) = 1 * 1 = 1 --> f(2) = 2

F(3,0) = 3
F(3,1) = f(1)*f(2) = 1 * 2 = 2 --> f(3) = 3

F(4,0) = 4
F(4,1) = f(1)*f(3) = 1 * 3 = 3
F(4,2) = f(2)*f(2) = 2 * 2 = 4 --> f(4) = 4

F(5,0) = 5
F(5,1) = f(1)*f(4) = 1 * 4 = 4
F(5,2) = f(2)*f(3) = 2 * 3 = 6 --> f(5) = 6

F(6,0) = 6
F(6,1) = f(1)*f(5) = 1 * 6 = 6
F(6,2) = f(2)*f(4) = 2 * 4 = 8
F(6,3) = f(3)*f(3) = 3 * 3 = 9 --> f(6) = 9

F(7,0) = 7
F(7,1) = f(1)*f(6) = 1 * 9 = 9
F(7,2) = f(2)*f(5) = 2 * 6 = 12
F(7,3) = f(3)*f(4) = 3 * 4 = 12 --> f(7) = 12

…………

当 N > 5 时，用数学归纳法可以证明，f(N) > N
　　f(5) > 5
　　f(6) > 6
　　若 f(N) > N 成立,
　　则 F(N + 1, 2) = f(2) * f(N - 2) > f(2) * (N - 2) = N + N - 4 > N + 1,
　　f(N + 1) >= F(N + 1, 2) > N + 1,
　　f(N + 1) > N + 1 也成立。
所以当 N >= 5 时，f(N) > N。
　　因此，对于任意 N >= 5,
　　f(N) = max {F(N, i), i > 0}
　　而 F(N, i) (i > 0) 总可以用 f(M) (1 <= M < N) 的乘积表示，以此类推，F(N, i) (i > 0) 总可以用 f(M) (1 <= M < 5) 的乘积表示，即 f(N) 总可以用 f(1), f(2), f(3) 和 f(4) 的乘积表示，而 f(4) = 2 * 2, 因此，对于任意 N, f(N) 总可以用 1, 2, 3 的乘积表示。

　　先写到这里，请大家继续，或者用别的方法证明。

kevin_cy

◆你说这是一个连三岁小孩都能明白的问题，好，那我问你，现在我们开的是紧急会议，大家正焦头烂额，谁还有时间、有心思去找一个三岁的小孩！？
    
刚看到的～ http://www.readfree.net/bbs/htm_data/6/0612/262818.html

bookish

给5楼醉兄一个例子：

N = 20
x1 = x2 = x3 = x4 = 5, x1 * x2 * x3 * x4 = 625
x1 = x2 = ...... = x10 = 2, x1 * x2 * ...... * x10 = 1024
x1 = x2 = x3 = x4 = x5 = x6 = 3, x7 = 2, x1 * x2 * ...... * x7 = 1458

呵呵，不均匀比均匀好。

醉乡常客

引用第8楼bookish于2006-12-10 21:41发表的“”:
给5楼醉兄一个例子：

N = 20
x1 = x2 = x3 = x4 = 5, x1 * x2 * x3 * x4 = 625
x1 = x2 = ...... = x10 = 2, x1 * x2 * ...... * x10 = 1024
.......

老大，要求是整数，20÷7肯定得分个2出来。

你能找到比3333332更均匀的划分吗？

bookish

能啊，11111111111111111111，2222222222，44444，5555，10 10

醉乡常客

引用第10楼bookish于2006-12-10 21:51发表的“”:
能啊，11111111111111111111，2222222222，44444，5555，10 10

我是说分7块的这种情况。3333332是最佳划分。

如果不强求整数，应该是20/7再七次方＝1554.26……最大，没错吧。（刚刚用计算器按的）

好像恍惚记得，这个乘积本来就是用来验证划分的均匀性的。

其它N，n是一样的，凡乘积取得最大值的，必然是均匀性最好的划分。

bookish

问题是，为什么分7块最大，而不是6块或8块。

N = 20，n = [N/3] = 6，N mod 3 = 2

若N mod 3 = 0, f(N)=power(3, n)
若N mod 3 = 1, f(N)=2*2*power(3, n-1)
若N mod 3 = 2, f(N)=2*power(3, n)

所以，f(20) = 2 * 3^6 = 2 * 3 * 3 * 3 * 3 * 3 * 3

我们需要证明这个公式

醉乡常客

引用第12楼bookish于2006-12-10 22:09发表的“”:
问题是，为什么分7块最大，而不是6块或8块。

N = 20，n = [N/3] = 6，N mod 3 = 2

若N mod 3 = 0, f(N)=power(3, n)
.......

你把问题整得更一般化了，我认为，给定n与否，是两个问题。

比如说，小学三年级某练习册上可能有这样一道题：把10分成哪两个整数的和，才能使这两个数的乘积最大？

而不会有这样一道题：把10分成哪几个整数的和，使它们的乘积最大？

bookish

引用第0楼caozhi700于2006-12-10 10:31发表的“小学数学题（结论简单，证明可不会）”:
  一个整数（大于等于5）任意分成几个整数之和，问如何分才能使这些数的乘积最大。

但楼主给我们的题目就是如此。:-)

醉乡常客

应该马上抓出来审问，到底要不要求这个“几”   

bookish

小学生不可能要求这个“几”，而是要学生了解，一组正数的几何平均值不超过它们的算术平均值，即

(x1·x2·……·xn)^(1/n) <= (x1+x2+……+xn)/n，等号只当x1=x2=……=xn时成立。

晚安，醉兄！明天继续给出证明。

yu_xin51

两个读书狂
拿茶社当自家书房
害得俺深更半夜
依然无法打烊
    
印象中，茶社从未出现过这样有学术色彩的帖子。
我所指的不是内容，而是形式。
    

iamken

321是正确的

bookish

caozhi700:
　　一个大于等于5的整数任意分成几个整数之和，问如何分才能使这些数的乘积最大。

醉乡常客:
　　设x1+x2+……+xn＝N（N≥5，n≥2，n、N和x1，x2，……，xn都是自然数），求满足x1·x2·……·xn取最大值的x1，x2，……，xn。

解：

设
　　N = x1 + x2 + …… + xn,

　　F(N,i) 属于 C(N) = {x1·x2·……·xn; n, x1，x2，……，xn 属于自然数, x1 + x2 + …… + xn = N} 中的一个元素,
　　F(N,0) = N
　　F(N,i) = f(i) * f(N - i) (i = 1, 2, ……, N - 1)

　　f(N) = max {F(N,i); 0 <= i < N}

首先证明　　f(N) = max {C(N)}

设　0 < N1 < N, N2 = N - N1, 那么，集合 C(N) 中的元素除了不分 (即，n = 1, x1 = N) 之外，总可以把 x 分成两大块，即 x1, x2, ……, xn1 和 x(n1+1)，x(n1+2)，……，x(n1+n2)，

　　C(N) = {G(N1) * G(N2), F(N,0); 0 < N1 < N, N2 = N - N1}

其中
　　G(N1) 的集合 {G(N1)} = C(N1) = {x1·x2·……·xn1; n1, x1，x2，……，xn1 属于自然数, x1 + x2 + …… + xn1 = N1}
　　G(N2) 的集合 {G(N2)} = C(N2) = {x(n1+1)·x(n1+2)·……·x(n1+n2); n2, x(n1+1)，x(n1+2)，……，x(n1+n2) 属于自然数, x(n1+1) + x(n1+2) + …… + x(n1+n2) = N2}
　　0 < N1 < N, N2 = N - N1, n1 + n2 = n
　　F(N,0) 是集合 C(N) 中的一个元素 (n = 1, x1 = N)。

用数学归纳法,

　　当 N = 1 时，集合 C 只有一个元素 (n = 1, x1 = 1), 其值为 1, 所以, f(1) = F(1,0) = 1 = max {C(1)}

设 f(N) = max {C(N)} 成立，那么，对于 N + 1,

　　max {C(N + 1)} = max {G(N1) * G(N2), F(N + 1,0); 0 < N1 < N + 1, N2 = N + 1 - N1}

因为
　　C(N1) = {G(N1)}, C(N2) = {G(N2)}, N1 < N + 1, N2 < N + 1

所以，f(N1) = max {C(N1)} = max {G(N1)}, f(N2) = max {C(N2)} = max {G(N2)}

　　max {C(N + 1)} = max {G(N1) * G(N2), F(N + 1,0); 0 < N1 < N + 1, N2 = N + 1 - N1}
　　= max {f(N1) * f(N2), F(N + 1,0); 0 < N1 < N + 1, N2 = N + 1 - N1}    (用 i 代替 N1)
　　= max {f(i) * f((N+1) - i), F(N+1,0); i = 1, 2, ……, (N+1) - 1)}
　　= max {F(N+1,i), F(N+1,0); i = 1, 2, ……, (N+1) - 1)}
　　= max {F(N+1,i); i = 0, 1, 2, ……, (N+1) - 1)}
　　= f(N+1)

所以，对于 N+1 也成立，得证。

下面证明，对于任意 N, f(N) 总可以用 1, 2, 3 的乘积表示。

F(1,0) = 1 --> f(1) = 1

F(2,0) = 2
F(2,1) = f(1)*f(1) = 1 * 1 = 1 --> f(2) = 2

F(3,0) = 3
F(3,1) = f(1)*f(2) = 1 * 2 = 2 --> f(3) = 3

F(4,0) = 4
F(4,1) = f(1)*f(3) = 1 * 3 = 3
F(4,2) = f(2)*f(2) = 2 * 2 = 4 --> f(4) = 4

F(5,0) = 5
F(5,1) = f(1)*f(4) = 1 * 4 = 4
F(5,2) = f(2)*f(3) = 2 * 3 = 6 --> f(5) = 6

F(6,0) = 6
F(6,1) = f(1)*f(5) = 1 * 6 = 6
F(6,2) = f(2)*f(4) = 2 * 4 = 8
F(6,3) = f(3)*f(3) = 3 * 3 = 9 --> f(6) = 9

F(7,0) = 7
F(7,1) = f(1)*f(6) = 1 * 9 = 9
F(7,2) = f(2)*f(5) = 2 * 6 = 12
F(7,3) = f(3)*f(4) = 3 * 4 = 12 --> f(7) = 12

当 N > 5 时，用数学归纳法可以证明，f(N) > N
　　f(5) > 5
　　f(6) > 6
　　若 f(N) > N 成立,
　　则 F(N + 1, 2) = f(2) * f(N - 2) > f(2) * (N - 2) = N + N - 4 > N + 1,
　　f(N + 1) >= F(N + 1, 2) > N + 1,
　　f(N + 1) > N + 1 也成立。
所以当 N >= 5 时，f(N) > N。
　　因此，对于任意 N >= 5,
　　f(N) = max {F(N, i), i > 0}
　　而 F(N, i) (i > 0) 总可以用 f(M) (1 <= M < N) 的乘积表示，以此类推，F(N, i) (i > 0) 总可以用 f(M) (1 <= M < 5) 的乘积表示，即 f(N) 总可以用 f(1), f(2), f(3) 和 f(4) 的乘积表示，而 f(4) = 2 * 2, 因此，对于任意 N, f(N) 总可以用 1, 2, 3 的乘积表示。

如果 x1, x2, ……, xn 中至少有一个 2 和一个 1, 设 f1(N) = x1·x2·……·x(n-2)·2·1, f2(N) = x1·x2·……·x(n-2)·3,
因为 f2(N) > f1(N), 所以可以把 x = 2 和 x = 1 合并成 x = 3。

如果 x1, x2, ……, xn 中没有 2，但至少有一个 1, 设 f1(N) = x1·x2·……·x(n-2)·3·1, f2(N) = x1·x2·……·x(n-2)·2·2,
因为 f2(N) > f1(N), 所以可以把 x = 3 和 x = 1 重新组合成两个 2。

重复以上过程，可以把 x = 1 全部去除，于是得到，

　　对于任意 N, f(N) 总可以用 2 和 3 的乘积表示。

如果 x1, x2, ……, xn 中至少有 3 个 2, 设 f1(N) = x1·x2·……·x(n-3)·2·2·2, f2(N) = x1·x2·……·x(n-3)·3·3,
因为 f2(N) > f1(N), 所以可以把 3 个 2 重新组合成两个 3。

重复以上过程，可以把 3 个以上的 2 全部去除，于是得到，

　　对于任意 N, f(N) 总可以用 2 和 3 的乘积表示，并且 2 的个数不超过两个。

若 N mod 3 = 0，那么不可能有 N = 3 * m + 2 或 N = 3 * m + 2 + 2 (m 为自然数), 因此, f(N) 只能是 3 的乘积, f(N) = 3^(N/3)

若 N mod 3 = 1，那么要使 2 不超过两个，并且没有 1，就只能有 N = 3 * m + 2 + 2 (m 为自然数), 因此, f(N) 只能是若干个 3 和两个 2 的乘积, f(N) = 3^((N-1)/3 - 1) * 2 * 2

若 N mod 3 = 2，那么要使 2 不超过两个，并且没有 1，就只能有 N = 3 * m + 2 (m 为自然数), 因此, f(N) 只能是若干个 3 和一个 2 的乘积, f(N) = 3^((N-2)/3) * 2

最终得到，

　　N mod 3 = 0: f(N) = f(N) = 3^(N/3)
　　N mod 3 = 1: f(N) = 3^((N-1)/3 - 1) * 2 * 2
　　N mod 3 = 2: f(N) = 3^((N-2)/3) * 2

感谢楼主出的题，对我们当老师的是一个挑战。这个证明太繁琐了。

感谢斑竹的奖励，为了交流和活跃学术气氛，如果有更好的证明，笨人愿将版主的奖励全部奉送！

PS: 笨人不是数学专业的，故上述证明中的写法及符号可能不规范或不对。