本帖最后由 业余的业余 于 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前者)的互异拆分。这个命题与楼主的算法等价。还是不证,感觉能走通。 |