yuange1975 发表于 2025-3-17 18:52:11

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

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

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





northwolves 发表于 2025-3-17 22:50:12

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

northwolves 发表于 2025-3-17 23:20:58

先从小的规模看看规律。
显然,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的答案.
MaxPartition(m)定义为降序是为了适应Mathematica的 IntegerPartitions[]函数,它给出的结果是降序的。
f:=MaximalBy[{m, Length@#, #, Times@@# Times@@Flatten[-Differences/@Subsets[#, {2}]]}&/@Select, DuplicateFreeQ], Last]);
f/@Range//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 发表于 2025-3-17 23:25:01

规律还是很明显的:
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 发表于 2025-3-17 23:41:51

v=({63, 62, 61, 60} + PadRight[#, 4])&/@IntegerPartitions;
取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}
MaximalBy[{#, Times@@Flatten[(-Differences /@Subsets[#, {2}])] Times@@Flatten@Outer]}&/@v, Last]
{{67,65,62,61}, 2860032858977174496177858424104172934419225827872581357288567464500229186689747931564049777500448361642115808026426987127380258139401458420689945007051091506957224000975907222589291514061602831031122209448462579065184151491165924036293319972278211699333030397832620691374798700701963149406896128000000000000000000000000000000000000000000000000000000000}

hujunhua 发表于 2025-3-18 08:36:34

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

mathe 发表于 2025-3-18 09:07:52

是的,题目并没有限制整数范围,在实数范围解决会更加具有一般性。当然要解决一般情况,复杂度会非常高。
如果我们限定只使用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 发表于 2025-3-18 10:00:12

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 发表于 2025-3-18 10:57:51

{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 发表于 2025-3-18 13:19:06

我们假设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\)。后面就是一个计算题了

页: [1] 2 3 4 5 6
查看完整版本: 悬赏挑战:求2025的两两之差乘积最大的堆磊数组