免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 将正整数$n$拆为两两互异的正整数之和,使积最大。

本帖最后由 abababa 于 2019-9-9 18:43 编辑

如题,将正整数$n$拆为两两互异的正整数之和,使拆分后的数的乘积最大,要怎么拆并证明?

我是以$2$为首项作一个公差为$1$的等差数列,$A=2+3+\cdots+k$,如果$A<n$,那再加上$k+1$,直到$A\ge n$。
如果$A=n$,那就拆为$2+\cdots+k$,如果$A>n$,去掉$2+\cdots+k$中的数$A-n$。
感觉这个就是积最大的,但要怎么证明?

补充一下,如果$A=n-1$,这时应该把差的$1$加到最大的数上,让序列变成$2+\cdots+(k-1)+(k+1)$。
如果$A=n+1$,那应该把$2$去掉,最大的数再加$1$。例如$n=8$,$A=n+1=2+3+4$,应该去掉$2$,把$4$加$1$。可行的拆分是$(1,2,5),(1,3,4),(2,6),(3,5)$,显然是$(3,5)$最大。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 青青子衿 于 2021-2-22 00:34 编辑

改为拆成互异素数的话,也有点好玩。
MaximalBy[
Select[IntegerPartitions[100, All, Prime[Range@PrimePi[100]]],
  DuplicateFreeQ], Times @@ # &]
Max @@ Times @@@
  Select[IntegerPartitions[100, All, Prime[Range@PrimePi[100]]],
   DuplicateFreeQ]

{{23, 19, 17, 13, 11, 7, 5, 3, 2}}
223092870

(前九个素数之和刚好为一百)

TOP

本帖最后由 业余的业余 于 2019-10-13 00:21 编辑

似乎这样更好走通:

首先,对足够大的 $n (n\ge 2)$, 互异拆分中不能含 $1$, 以下讨论都隐含互异拆分中不含元素 $1$ 这一条件。互异拆分中的数按从小到大排列,称第 $i$ 个元素和 第 $i+1$ 的元素为相邻元素。则

定义: $n$ 的 $m$-最大积互异拆分, 是这样一个集合:
1.它的所有元素都是大于$1$的正整数,且两两不同;
2. 它的基数为 $m$
3. 它所有元素之和为 $n$
4. 在所有满足前面3个条件的集合中,它的所有元素之积最大。

断点: 设 $\{a_1, a_2,\cdots, a_m\}$ 是一个互异拆分,且 $a_i<a_{i+1}\forall 1\le i <m$。 如果  $a_{k+1}-a_k>1 (1\le k <m)$, 则称两元素间有一个断点。

命题1': m-最大积互异拆分相邻元素之差不大于 $2$.
证明: 反证法。设 $a_1, a_2, ..., a_m$ 构成 $n$ 的$m$-最大积互异拆分,且  $a_{i+1}-a_i>2 (0\le i<m)$, 那么可以通过把 $a_i$加$1$, $a_{i+1}$减$1$ 得到 $n$ 的另一个合法的$m$-互异差分,且新拆分与原拆分元素积之比$=\frac{(a_i+1)(a_{i+1}-1)}{a_i a_{i+1}}>1$( 因为 $(a_i+1)(a_{i+1}-1)-a_i a_{i+1}=a_{i+1}-a_i-1>0$), 这与原拆分是最大积互异拆分的题设矛盾。故假设不成立,命题为真。

命题2': 最大积互异拆分中不能含有多于一个断点.
证明方法与上面相似,略。举个例子说明 $\{2,3,(断点)5,6,(断点)8,9\}$, 替换为$\{2,4,5,6,7,9\}$ 显然得到更大积 $(3\times 8<4\times 7)$. 而后者显然任然不是最大积互异拆分,因为依然有两个断点.


命题3': 假定 $n$ 存在 $m$-互异拆分和 $(m+1)$-互异拆分,则其 $(m+1)$-最大积互异拆分的元素积大于其$m$-最大积互异拆分的元素积。
设 $\{a_1, a_2,\cdots,a_m\}$ 是$n$ 的$m$-最大积拆分
证明的思路是因为 $n$ 可以做$(m+1)$-互异拆分,那么它的$m$-最大积互异拆分$S$不能含有$2$,且如果 $S$ 包含 $3$, 断点后的元素至少有2个。分情况,引入新元素 $2$, 并对现有的某个元素做相应调整(使元素和不变), 可以证明这个新构造出的$(m+1)$-互异拆分有更大的元素积。而这个拆分的元素积不大于 $m+1-$最大积互异拆分。由此命题得证。

上面是个大体的思路,应该是可以走通的。举例子形象说明意思。

$\{3,4,5,7,8\}\to \{\mathbf{2},3,4,5,7,\mathbf{8-2}\}=\{2,3,4,5,6,7\}$ 显然有 $2\times 6 > 8$
$\{3,4,5,7\}$不可能有 $5$-互异拆分. 很容易证明第$m$个结点是可以做$m$拆分的最小整数。而 $3+4+5+7=19<20$(第$5$结点).
$\{2,3,4,\cdots, i, i+2, \cdots, m+2\}$(中间恰有一个断点) 不可能有$(m+1)$-拆分,理由同上。
从上面的例子已经足够构造出这个命题的完整证明的,我感觉。


命题4‘: 最大积互异拆分是基数最大且最大元素最小(其实只保留后者就可以了,后者implies前者)的互异拆分。这个命题与楼主的算法等价。还是不证,感觉能走通。

TOP

本帖最后由 业余的业余 于 2019-10-10 01:05 编辑

命题3的证明可以用这样的思路。$n$的任一 $m$ 个元素的拆分 $T$,可以以相邻集合两两不同的方式组成一个链条,从 $T$按积单调增加的方式 走到最大积互异拆分。因为相邻集合仅两个元素不同,设分别为 a,b 和 c,d. 显然有 a+b=c+d. 而最大积拆分可以保证a,b(或c,d)之差为最小(a,b,c,d中的最大数最小),从而使积更大。

TOP

abababa 基本已经给出了完整的算法。

定义:
整数的互异拆分: 对正整数 $n$, 从集合 $\{1,2,3, \cdots, n\}$ 中选择一个非空子集,使得该子集 $S$ 的元素和为 $n$, 则称集合 $S$ 为 $n$ 的一个 互异拆分

最大积互异拆分: 在 $n$ 的所有互异拆分中,使得集合$S$ 中所有元素的乘积最大的互异拆分,称为$n$的最大积拆分

结点: 对正整数 $n$, 如果存在正整数 $m$, 使得 $\displaystyle n=\sum_{i=2}^{m+1}$, 则称 $n$ 为一个结点。在需要区分结点时,也称 $n$ 为$m$个结点。显然,第 $m$ 的结点是结点的无穷集合 $\{2,5,9,14,20,\cdots\}$ 中的元素按从小到大排序的序号。

命题1: 当$n>1$ 时,其最大积拆分不含元素$1$. 用反证法易证,证略。

命题2: 如果 $n$ 是第 $m$ 个结点, 那么$n$ 的最大积拆分是 $\{2,3,\cdots,m+1\}$ 证略。

命题3:如果 $n$ 是第 $m$ 个结点和第 $m+1$ 个结点之间的整数(不包含), 那么其最大积拆分中有 $m$ 个元素 (就低不就高)。特别的,记第$m+1$ 的结点对应的整数为 $p$, 如果 $p-n>1$, 那么$n$ 的最大集拆分是 $p$ 的最大集拆分去掉 $p-n$ 后的集合;如果 $p-n=1$ 那么 $n$ 的最大积拆分是 $p$ 的最大集拆分中去掉 $2$和$m+2$, 加入 $m+3$后得到的集合。

TOP

本帖最后由 青青子衿 于 2019-10-9 12:01 编辑

回复 4# 青青子衿
100=2+3+5+6+7+8+9+10+11+12+13+14;
21794572800=2*3*5*6*7*8*9*10*11*12*13*14.
https://oeis.org/A034893
...

TOP

回复 1# abababa
MaximalBy[Select[IntegerPartitions[30], DuplicateFreeQ], Times @@ # &]
Max @@ Times @@@ Select[IntegerPartitions[30], DuplicateFreeQ]

{{8, 7, 6, 4, 3, 2}}
8064

TOP

回复 2# realnumber

$30=(2+3+4+5+6+7+8)-5=(2+3+4+5+6+9)$

为什么$30$要拆成$2+3+4+6+7+8$,不拆成$2+3+4+5+6+9$或其它形式?为什么略过的数必须是连续正整数之和与$30$的差$5$?略过其它数不行吗?
楼上的第3条,为什么必须拆出$3$来,略过$3$不行吗?以下用括号表示里面的数的积:得证明$(2,3,m-5)>(2,4,m-6)$,但对于$m \ge 9$这就不成立,因为这时它要继续拆分才行,就得证明下一个不等式$(2,3,4,m-9)>(2,4,5,m-11)和(2,4,6,m-12)$等等。

TOP

我觉得你其实已经说得很明白了,
1.首先不能拆一个1出来,m=1+(m-1),乘积1(m-1)<m,所以至少从2开始拆.
2.而m=2+(m-2)<2(m-2),m>4(m不大于4的话就不拆开),也就是说m>4的话就可以拆一个2出来.
3.m=2+3+((m-2)-3)<2(m-2)<2×3×(m-2-3),(m>8)
依次类推,不小于2的两不同数的乘积总大于和,总是尽可能拆出一个从2开始的等差数列,受制于拆成不同的数,比如10=2+3+4+1,最后的1,不够拆开,无法加在2,3,只能加在4上,变成5,
又11=2+3+4+2=2+4+5,也可解释为多余的2平分在最大的两个数上.
t(t-1)>(t+1)(t-2)>(t+2)(t-3)....,其中每个括号都正.

TOP

返回列表 回复 发帖