悬赏挑战：求2025的两两之差乘积最大的堆磊数组

yuange1975

把2025分成若干非负数之和，使得这些数两两之差的乘积最大。

可以使用程序和数学软件等，答案需要过程和结果，使用程序需要提供代码。

northwolves

显然拆分情况中不能有重复数字出现，而2025有175682591152509068088152170718336 种不同数字的拆分方式，计算量太恐怖了

northwolves

先从小的规模看看规律。
显然，0是白给的（增大乘积，不涨规模），假定 m 的最大分解为 `m=x_0+x_1+...+x_n, x_0<x_1<...<x_n`, 则必有`x_0=0`.
且记MaxPartition(m)=${x_n,x_{n-1},...,x_2, x_1}$(省略了`x_0`), 下面的程序给出了m=1~91的答案.

1. f[m_]:=MaximalBy[{m, Length@#, #, Times@@# Times@@Flatten[-Differences/@Subsets[#, {2}]]}&/@Select[IntegerPartitions[m], DuplicateFreeQ], Last]);
   
2. f/@Range[91]//Tableform[#, Tabledepth->1 ]&

复制代码

{{m, n, {x_n, ..., x_2, x_1}, 最大积}}
{{1,1,  {1},  1}}
{{2,1,  {2},  2}}
{{3,1,  {3},  3}}
{{4,2,  {3,1},  6}}
{{5,2,  {4,1},  12}}
{{6,2,  {5,1},  20}}
{{7,3,  {4,2,1},  48}}
{{8,3,  {5,2,1},  120}}
{{9,3,  {6,2,1},  240},    {9,3,  {5,3,1},  240}}
{{10,3,  {6,3,1},  540}}
{{11,4,  {5,3,2,1},  1440}}
{{12,4,  {6,3,2,1},  4320}}
{{13,4,  {6,4,2,1},  11520}}
{{14,4,  {7,4,2,1},  30240}}
{{15,4,  {8,4,2,1},  64512}}
{{16,5,  {6,4,3,2,1},  207360}}
{{17,5,  {7,4,3,2,1},  725760}}
{{18,5,  {7,5,3,2,1},  2419200}}
{{19,5,  {8,5,3,2,1},  7257600}}
{{20,5,  {9,5,3,2,1},  17418240}}
{{21,5,  {9,6,3,2,1},  39191040}}
{{22,6,  {7,5,4,3,2,1},  174182400}}
{{23,6,  {8,5,4,3,2,1},  696729600}}
{{24,6,  {8,6,4,3,2,1},  2786918400}}
{{25,6,  {9,6,4,3,2,1},  9405849600}}
{{26,6,  {10,6,4,3,2,1},  25082265600}}
{{27,6,  {10,7,4,3,2,1},  65840947200}}
{{28,6,  {10,7,5,3,2,1},  182891520000}}
{{29,7,  {8,6,5,4,3,2,1},  1003290624000}}
{{30,7,  {9,6,5,4,3,2,1},  4514807808000}}
{{31,7,  {9,7,5,4,3,2,1},  21069103104000}}
{{32,7,  {10,7,5,4,3,2,1},  79009136640000}}
{{33,7,  {11,7,5,4,3,2,1},  231760134144000}}
{{34,7,  {11,8,5,4,3,2,1},  695280402432000}}
{{35,7,  {11,8,6,4,3,2,1},  2317601341440000}}
{{36,7,  {12,8,6,4,3,2,1},  6356849393664000}}
{{37,8,  {9,7,6,5,4,3,2,1},  45509262704640000}}
{{38,8,  {10,7,6,5,4,3,2,1},  227546313523200000}}
{{39,8,  {10,8,6,5,4,3,2,1},  1213580338790400000}}
{{40,8,  {11,8,6,5,4,3,2,1},  5006018897510400000}}
{{41,8,  {12,8,6,5,4,3,2,1},  16019260472033280000}}
{{42,8,  {11,9,7,5,4,3,2,1},  56067411652116480000}}
{{43,8,  {12,9,7,5,4,3,2,1},  210252793695436800000}}
{{44,8,  {13,9,7,5,4,3,2,1},  624751158409297920000}}
{{45,9,  {9,8,7,6,5,4,3,2,1},  1834933472251084800000}}
{{46,9,  {10,8,7,6,5,4,3,2,1},  18349334722510848000000}}
{{47,9,  {11,8,7,6,5,4,3,2,1},  100921340973809664000000}}
{{48,9,  {11,9,7,6,5,4,3,2,1},  605528045842857984000000}}
{{49,9,  {12,9,7,6,5,4,3,2,1},  2724876206292860928000000}}
{{50,9,  {13,9,7,6,5,4,3,2,1},  9446237515148584550400000}}
{{51,9,  {12,10,8,6,5,4,3,2,1},  38753794933942910976000000}}
{{52,9,  {13,10,8,6,5,4,3,2,1},  157437291919143075840000000}}
{{53,9,  {14,10,8,6,5,4,3,2,1},  503799334141257842688000000}}
{{54,9,  {14,11,8,6,5,4,3,2,1},  1558629189999516450816000000}}
{{55,10,  {10,9,8,7,6,5,4,3,2,1},  6658606584104736522240000000}}
{{56,10,  {11,9,8,7,6,5,4,3,2,1},  73244672425152101744640000000}}
{{57,10,  {12,9,8,7,6,5,4,3,2,1},  439468034550912610467840000000}}
{{58,10,  {12,10,8,7,6,5,4,3,2,1},  2929786897006084069785600000000}}
{{59,10,  {13,10,8,7,6,5,4,3,2,1},  14282711122904659840204800000000}}
{{60,10,  {14,10,8,7,6,5,4,3,2,1},  53322121525510730070097920000000}}
{{61,10,  {13,11,9,7,6,5,4,3,2,1},  251375715763122013187604480000000}}
{{62,10,  {14,11,9,7,6,5,4,3,2,1},  1099768756463658807695769600000000}}
{{63,10,  {15,11,9,7,6,5,4,3,2,1},  3770635736446830197814067200000000}}
{{64,10,  {15,12,9,7,6,5,4,3,2,1},  12725895610508051917622476800000000}}
{{65,10,  {16,12,9,7,6,5,4,3,2,1},  39591675232691717077047705600000000}}
{{66,11,  {11,10,9,8,7,6,5,4,3,2,1},  265790267296391946810949632000000000}}
{{67,11,  {12,10,9,8,7,6,5,4,3,2,1},  3189483207556703361731395584000000000}}
{{68,11,  {13,10,9,8,7,6,5,4,3,2,1},  20731640849118571851254071296000000000}}
{{69,11,  {13,11,9,8,7,6,5,4,3,2,1},  152032032893536193575863189504000000000}}
{{70,11,  {14,11,9,8,7,6,5,4,3,2,1},  798168172691065016273281744896000000000}},
{{71,11,  {15,11,9,8,7,6,5,4,3,2,1},  3192672690764260065093126979584000000000},
  {71,11,  {14,12,9,8,7,6,5,4,3,2,1},  3192672690764260065093126979584000000000},  
  {71,11,  {14,11,10,8,7,6,5,4,3,2,1},  3192672690764260065093126979584000000000}}
{{72,11,  {14,12,10,8,7,6,5,4,3,2,1},  17027587684076053680496677224448000000000}}
{{73,11,  {15,12,10,8,7,6,5,4,3,2,1},  79816817269106501627328174489600000000000}}
{{74,11,  {16,12,10,8,7,6,5,4,3,2,1},  291901503155589491665657323847680000000000}}
{{75,11,  {16,13,10,8,7,6,5,4,3,2,1},  1067264870912624078902559590318080000000000}}
{{76,11,  {17,13,10,8,7,6,5,4,3,2,1},  3527903323294507371927905312440320000000000}}
{{77,11,  {16,13,11,9,7,6,5,4,3,2,1},  13696565843378675679249514742415360000000000}}
{{78,12,  {12,11,10,9,8,7,6,5,4,3,2,1},  127313963299399416749559771247411200000000000}}
{{79,12,  {13,11,10,9,8,7,6,5,4,3,2,1},  1655081522892192417744277026216345600000000000}}
{{80,12,  {14,11,10,9,8,7,6,5,4,3,2,1},  11585570660245346924209939183514419200000000000}}
{{81,12,  {14,12,10,9,8,7,6,5,4,3,2,1},  92684565281962775393679513468115353600000000000}}
{{82,12,  {15,12,10,9,8,7,6,5,4,3,2,1},  521350679711040611589447263258148864000000000000}}
{{83,12,  {15,12,11,9,8,7,6,5,4,3,2,1},  2293942990728578690993567958335855001600000000000}}
{{84,12,  {15,13,11,9,8,7,6,5,4,3,2,1},  13253892835320676881296170425940495564800000000000}}
{{85,12,  {16,13,11,9,8,7,6,5,4,3,2,1},  66269464176603384406480852129702477824000000000000}}
{{86,12,  {17,13,11,9,8,7,6,5,4,3,2,1},  257504203657658865122325596846843913830400000000000}}
{{87,12,  {17,14,11,9,8,7,6,5,4,3,2,1},  1013922801902031781419157037584447910707200000000000}}
{{88,12,  {18,14,11,9,8,7,6,5,4,3,2,1},  3548729806657111234967049631545567687475200000000000},  
  {88,12,  {17,14,11,10,8,7,6,5,4,3,2,1},  3548729806657111234967049631545567687475200000000000}}
{{89,12,  {17,14,12,10,8,7,6,5,4,3,2,1},  15772132474031605488742442806869189722112000000000000}}
{{90,12,  {18,14,12,10,8,7,6,5,4,3,2,1},  57680941619315585787400933693693036698009600000000000}}
{{91,13,  {13,12,11,10,9,8,7,6,5,4,3,2,1},  792786697595796795607377086400871488552960000000000000}}

northwolves

规律还是很明显的：
1、若m=(n+(n-1)+...+3+2+1), n≥9, 则 MaxPartition(m)={n,n-1, ..., 3, 2, 1}.
2、若m=1+(n+(n-1)+...+3+2+1), 则MaxPartition(m)={n+1,n-1, ..., 3, 2, 1}.
3、若m=k+(n+(n-1)+...+3+2+1), k<n+1, 则MaxPartition(m)=MaxPartition(k)+{n, n-1, ..., 3, 2, 1}. 表左对齐相加。
      第3条在 k 远离三角数时一般成立，接近三角数时有例外，补差表要基于MaxPartition(k)进行微调。

按照以上规律，2025=9+(63+62+...+3+2+1), 所以MaxPartition(2025)≈{5,3,1}+{63, 62, 61, 60, ..., 3, 2, 1}
但是 9 接近三角形数10，补差表{5,3,1}可能需要微调，猜想可能是{4,3,1,1}，即可能
MaxPartition(2025)={4,3,1,1}+{63, 62, 61, 60, ..., 3, 2, 1}={67, 65, 62, 61, 59~1};
我们下面搜索{x3, x2, x1, x0}+{63, 62, 61, 60, 59, ..., 3, 2, 1}。

northwolves

1. v=({63, 62, 61, 60} + PadRight[#, 4])&/@IntegerPartitions[9, 4];

复制代码

取0-59，剩余四个数字有18种组合：
{{72, 62, 61, 60}, {71, 63, 61, 60}, {70, 64, 61, 60}, {70, 63, 62, 60}, {69, 65, 61, 60}, {69, 64, 62, 60}, {69, 63, 62, 61}, {68, 66, 61, 60}, {68, 65, 62, 60}, {68, 64, 63, 60}, {68, 64, 62, 61}, {67, 66, 62, 60}, {67, 65, 63, 60}, {67, 65, 62, 61}, {67, 64, 63, 61}, {66, 65, 64, 60}, {66, 65, 63, 61}, {66, 64, 63, 62}}
最大的果然是{67,65,62,61}

1. MaximalBy[{#, Times@@Flatten[(-Differences /@Subsets[#, {2}])] Times@@Flatten@Outer[Subtract, #, Range[0, 59]]}&/@v, Last]

复制代码

{{67,65,62,61}, 2860032858977174496177858424104172934419225827872581357288567464500229186689747931564049777500448361642115808026426987127380258139401458420689945007051091506957224000975907222589291514061602831031122209448462579065184151491165924036293319972278211699333030397832620691374798700701963149406896128000000000000000000000000000000000000000000000000000000000}

hujunhua

题目没有限制必须是整数，放开到实数范围也不会发散到无穷大。

mathe

是的，题目并没有限制整数范围，在实数范围解决会更加具有一般性。当然要解决一般情况，复杂度会非常高。
如果我们限定只使用n个数字，那么这时n个数字的和S并不重要，如果限定\(x_0+x_1+...+x_{n-1}=1\), 得到乘积最大值为\(c_n\),那么限定和为S,乘积最大值显然为\(c_n S^{\frac{n(n-1)}2}\).
所以我们需要求出各\(c_n\). 另外显然我们总应该选择\(x_0=0\).
于是\(c_2=1\),这时\(x_0=0,x_1=1\).
而对于\(c_3\), 由于乘积为\(x_1x_2(x_2-x_1)\)要求\(x_1+x_2=1\).得到取极值时\(6x_1^2-6x_1+1=0\),得到这时乘积为\(c_3=\frac{1-2x_1}6 \approx 0.096\)，
    对应\(x_0=0,x_1=0.21132486540518711774542560974902127218, x_2=0.78867513459481288225457439025097872783\)
而对于\(c_4\),由于乘积为\(x_1x_2x_3(x_3-x_2)(x_3-x_1)(x_2-x_1)\),要求\(x_1+x_2+x_3=1\), 经计算，取最小值时要求\(72x_1^3-72x_1^2+18x_1-1=0\), 对应\(c_4\approx 0.0005787...\).
    对应\(x_0=0,x_1=0.077985185627007321599202449814861108688, x_2=0.27545060744435655038276112441022840133, x_3=0.64656420692863612801803642577491048998\)

northwolves

1        {{1,0},1}
2        {{2,0},2}
3        {{3,0},3}
4        {{$\frac{2}{3} \left(\sqrt{3}+3\right)$,$\frac{2}{3} \left(\sqrt{3}-3\right)$,0},$\frac{32}{3 \sqrt{3}}$)}
5        {{$\frac{5}{6} \left(\sqrt{3}+3\right)$,$\frac{5}{6} \left(\sqrt{3}-3\right)$,0},$\frac{125}{6 \sqrt{3}}$}

northwolves

{6,27.,{0,0.467911,1.6527,3.87939},4}
{7,68.0839,{0,0.545896,1.92815,4.52595},4}
{8,162.065,{0,0.297317,1.02865,2.29247,4.38156},5}
{9,526.276,{0,0.334481,1.15724,2.57903,4.92925},5}
{10,1509.35,{0,0.371646,1.28582,2.86559,5.47695},5}
{11,5432.99,{0,0.226245,0.774754,1.69064,3.07966,5.2287},6}
{12,20038.6,{0,0.246812,0.845186,1.84433,3.35963,5.70404},6}
{13,73763.2,{0,0.163326,0.555998,1.19991,2.14154,3.47738,5.46185},7}
{14,349718.,{0,0.175889,0.598767,1.29221,2.30627,3.74487,5.88199},7}
{15,1.48917*10^6,{0,0.188453,0.641536,1.38451,2.47101,4.01236,6.30213},7}
{16,7.93528*10^6,{0,0.131721,0.446739,0.957729,1.69037,2.69163,4.05548,6.02634},8}
{17,4.33284*10^7,{0,0.139954,0.47466,1.01759,1.79602,2.85986,4.30894,6.40298},8}
{18,2.32145*10^8,{0,0.102346,0.346241,0.739064,1.29549,2.04043,3.01751,4.31243,6.14649},9}
{19,1.62584*10^9,{0,0.108032,0.365476,0.780123,1.36746,2.15378,3.18515,4.55201,6.48796},9}
{20,1.03045*10^10,{0,0.113718,0.384712,0.821182,1.43943,2.26714,3.35279,4.79159,6.82943},9}
{21,5.9682*10^10,{0,0.119404,0.403948,0.862241,1.5114,2.3805,3.52043,5.03117,7.1709},9}
{22,3.18541*10^11,{0,0.125089,0.423183,0.9033,1.58337,2.49386,3.68807,5.27075,7.51238},9}
{23,1.57816*10^12,{0,0.130775,0.442419,0.944359,1.65534,2.60721,3.85571,5.51033,7.85385},9}
{24,7.30388*10^12,{0,0.136461,0.461654,0.985418,1.72731,2.72057,4.02335,5.74991,8.19532},9}
{25,3.17533*10^13,{0,0.142147,0.48089,1.02648,1.79929,2.83393,4.19099,5.98949,8.53679},9}
{26,1.75356*10^14,{0,0.108802,0.367658,0.78371,1.38068,2.12798,3.09811,4.3299,5.9055,7.89766},10}
{27,9.22781*10^14,{0,0.112987,0.381799,0.813852,1.43378,2.20983,3.21726,4.49644,6.13263,8.20142},10}
{28,4.57137*10^15,{0,0.117172,0.395939,0.843995,1.48689,2.29167,3.33642,4.66297,6.35977,8.50517},10}
{29,2.14094*10^16,{0,0.121357,0.41008,0.874138,1.53999,2.37352,3.45558,4.82951,6.5869,8.80893},10}
{30,9.51542*10^16,{0,0.125541,0.424221,0.90428,1.59309,2.45536,3.57474,4.99604,6.81404,9.11268},10}

分割了30个数，似乎也没什么规律，直觉分割数与e或者$\sqrt3$相关

mathe

我们假设n+1个数情况各数分别为\(0=x_0 \lt x_1 \lt x_2 \lt \cdots \lt x_n\),而且\(\sum_{h=1}^nx_h=1\)
我们要求让\(\ln(\prod_{0\le i \lt j\le n}(x_j-x_i))\)最大， 于是根据拉格朗日乘数法，容易得出
\(\sum_{j \neq t}\frac1{x_j-x_t}=C \) 对所有的\(1\le t\le n\)都成立。
记\(f(x)=\prod_{i=0}^n(x-x_i)\), 于是容易得出\(f'(x_t)=\prod_{i\neq t}(x_t-x_i), f''(x_t)=2\sum_{h\neq t} \prod_{s\neq t, s\neq h} (x_t-x_s)\)
由此，我们得出\(\frac{f''(x_t)}{f'(x_t)} = 2\sum_{h\neq t} \frac 1{x_h-x_t}=2C\)
于是我们得到\(f'(x_t)-\frac{f''(x_t)}{2C}=0\)对一切\(1\le t \le n\)都成立，由于\(f'(x)-\frac{f''(x)}{2C}\)是一个n次多项式，由此得到
\(f'(x)-\frac{f''(x)}{2C}=(n+1)\frac{f(x)}x\)

现在我们假设\(f(x)=x^{n+1}+a_1 x^n+a_2 x^{n-1}+\cdots+a_{n-1}x^2+a_nx\)
于是\(f'(x)=(n+1)x^n+na_1x^{n-1}+(n-1)a_2x^{n-2}+\cdots+2a_{n-1}x+a_n\)
\(f''(x)=(n+1)nx^{n-1}+n(n-1)a_1x^{n-2}+(n-1)(n-2)a_2x^{n-3}+\cdots+2a_{n-1}\)
对比系数，得到
\((h-1)a_{h-1} = -\frac{(n-h+3)(n-h+2)}{2C}a_{h-2}\),其中\(a_0=1, 2\le h\le n+1\)
然后根据\(\sum_{h=1}^nx_h=1\)可以得到\(a_1=-1\)由此可以得出\(C=\frac{(n+1)n}2\)。后面就是一个计算题了