关于算术堆垒的一个猜想的弱化命题
我们将包括 n 个 1 、加、乘和括号的算术式所能得到的最大正整数称为 n 个 1 的极大算术堆垒，并记为f(+,×;n).易知，对于大于5的n, 若n=3a+2b, (b=0,1,2), 则f(+,×;n)=2^b·3^a.
f(+,×;n)有许多奇妙的性质，也有一些困难而引人注目的猜想，可以通过搜索“整数的复杂度”（最好是对应的英文）找到有关文献。
但我的猜想与那些奇妙的性质和引人注目的猜想都不相同，我的猜想如下：
--------------------------------------------------------------------------------------
裴进兵猜想（弱化）：n≥4时， f(+,×;n)可以表为任意 n 个较小正整数的四则运算.
例如：f(+,×;11)=54, 从1到54任意选取11个数譬如9、20、24、25、26、32、16、18、33、37、41，由下式可得到54，
9×(24-18)+(20+37)-(16+41)+(26+32)-(25+33)=54
上述猜想是我先前曾在本坛发过的一帖《整数的四则分解与堆垒》中提出过一个猜想的弱化。
那个帖子被引导至其它问题讨论上，反而忽略了其中主题猜想，故在此再次单独提出来一个弱化命题。
我的邮箱是peijinbing@sina.com,peijinbing@163.com, QQ：2756772317, 416478682
非常诚恳的邀请大家联系我
以n=4,5为例（穷举证明）
f(+,×;4)=4, 共有35种组合：组合（1） 1111------1+1+1+1=4
组合（2） 1112------1*1+1+2=4
组合（3） 1113------1*1*1+3=4
组合（4） 1114------1*1*1*4=4
组合（5） 1122------1*1*2*2=4
组合（6） 1123------(1+1)/2+3=4
组合（7） 1124------1+1-2+4=4
组合（8） 1133------(-1-1+3)+3=4
组合（9） 1134------(-1-1+3)*4=4
组合（10）1144------(1-1)*4+4=4
组合（11）1222------(-1+2)*2*2=4
组合（12）1223------1+2-2+3=4
组合（13）1224------1*(2-2)+4=4
组合（14）1233------(-1*2)+3+3=4
组合（15）1234------1+2-3+4=4
组合（16）1244------(-1-2+4)*4=4
组合（17）1333------1+3-3+3=4
组合（18）1334------1*(3-3)+4=4
组合（19）1344------1+3-4+4=4
组合（20）1444------1*(4-4)+4=4
组合（21）2222------2+2+2-2=4
组合（22）2223------2+2*(-2+3)=4
组合（23）2224------2*(2-2)+4=4
组合（24）2233------2+2+3-3=4
组合（25）2234------(2-2)*3+4=4
组合（26）2244------(2-2)*4+4=4
组合（27）2333------2+3-3/3=4
组合（28）2334------2*(3-3)+4=4
组合（29）2344------2+3-4/4=4
组合（30）2444------2*(4-4)+4=4
组合（31）3333------(3*3+3)/3=4
组合（32）3334------3*(3-3)+4=4
组合（33）3344------(3-3)*4+4=4
组合（34）3444------3*(4-4)+4=4
组合（35）4444------4*(4-4)+4=4
f(+,×;5)=6, 共有252种组合：
组合（1）11111------(1+1)*(1+1+1)=6
组合（2）11112------1*(1+1+1)*2=6
组合（3）11113------1*1*(1+1)*3=6
组合（4）11114------1*1*(1+1)+4=6
组合（5）11115------1*1*1*1+5=6
组合（6）11116------1*1*1*1*6=6
组合（7）11122------1*(1+1)+2+2=6
组合（8）11123------1*1*1*2*3=6
组合（9）11124------1*1*1*2+4=6
组合（10） 11125------1-1-1+2+5=6
组合（11） 11126------(1-1)*1*2+6=6
组合（12） 11133------1*1*1*3+3=6
组合（13） 11134------1-1-1+3+4=6
组合（14） 11135------(1+1+1)/3+5=6
组合（15） 11136------(1-1)*1*3+6=6
组合（16） 11144------1*(-1-1)+4+4=6
组合（17） 11145------1+(1-1)*4+5=6
组合（18） 11146------(1-1)*1*4+6=6
组合（19） 11155------1+(1-1)*5+5=6
组合（20） 11156------(1-1)*1*5+6=6
组合（21） 11166------(1-1)*1*6+6=6
组合（22） 11222------1*1*2*2+2=6
组合（23） 11223------1+1-2+2*3=6
组合（24） 11224------1+1-2+2+4=6
组合（25） 11225------1+1*(2-2)+5=6
组合（26） 11226------1-1+2-2+6=6
组合（27） 11233------1+1-2+3+3=6
组合（28） 11234------(1-1)*4+2*3=6
组合（29） 11235------1+1+2-3+5=6
组合（30） 11236------(1-1)*2*3+6=6
组合（31） 11244------(-1*1*2)+4+4=6
组合（32） 11245------[(1+1)*2]/4+5=6
组合（33） 11246------(1-1)*2*4+6=6
组合（34） 11255------[-(1+1)*2]+5+5=6
组合（35） 11256------(1-1)*2*5+6=6
组合（36） 11266------(1-1)*2*6+6=6
组合（37） 11333------(1-1)*3+3+3=6
组合（38） 11334------(1-1)*4+3+3=6
组合（39） 11335------(1-1)*5+3+3=6
组合（40） 11336------(1-1)*6+3+3=6
组合（41） 11344------1*1-3+4+4=6
组合（42） 11345------1+1+3-4+5=6
组合（43） 11346------(1-1)*3*4+6=6
组合（44） 11355------(1+1)*3+5-5=6
组合（45） 11356------(1-1)*3*5+6=6
组合（46） 11366------(1-1)*3*6+6=6
组合（47） 11444------1+1+4+4-4=6
组合（48） 11445------1+1*(4-4)+5=6
组合（49） 11446------1-1+4-4+6=6
组合（50） 11455------1+1+4-5+5=6
组合（51） 11456------(1-1)*4*5+6=6
组合（52） 11466------(1-1)*4*6+6=6
组合（53） 11555------1+1*(5-5)+5=6
组合（54） 11556------1-1+5-5+6=6
组合（55） 11566------(1-1)*5*6+6=6
组合（56） 11666------1-1+6-6+6=6
组合（57） 12222------(-1+2)*2+2+2=6
组合（58） 12223------1*(2-2)+2*3=6
组合（59） 12224------1*(2-2)+2+4=6
组合（60） 12225------1+(2-2)*2+5=6
组合（61） 12226------1*(2-2)*2+6=6
组合（62） 12233------1*(2-2)+3+3=6
组合（63） 12234------1+2+2-3+4=6
组合（64） 12235------1+(2-2)*3+5=6
组合（65） 12236------1*(2-2)*3+6=6
组合（66） 12244------(1+2)*2+4-4=6
组合（67） 12245------1+(2-2)*4+5=6
组合（68） 12246------1*(2-2)*4+6=6
组合（69） 12255------1+(2-2)*5+5=6
组合（70） 12256------1*(2-2)*5+6=6
组合（71） 12266------1*(2-2)*6+6=6
组合（72） 12333------1+2+3+3-3=6
组合（73） 12334------1*2+3-3+4=6
组合（74） 12335------1+2*(3-3)+5=6
组合（75） 12336------1*2*(3-3)+6=6
组合（76） 12344------1+2+3+4-4=6
组合（77） 12345------1+2*3+4-5=6
组合（78） 12346------1-2-3+4+6=6
组合（79） 12355------1*2*3+5-5=6
组合（80） 12356------1*2+3-5+6=6
组合（81） 12366------1*2*3+6-6=6
组合（82） 12444------1*2+4+4-4=6
组合（83） 12445------1+2*(4-4)+5=6
组合（84） 12446------1*2*(4-4)+6=6
组合（85） 12455------1*2+4+5-5=6
组合（86） 12456------1-2-4+5+6=6
组合（87） 12466------1*2+4+6-6=6
组合（88） 12555------1+2*(5-5)+5=6
组合（89） 12556------1*2*(5-5)+6=6
组合（90） 12566------1-2-5+6+6=6
组合（91） 12666------1*2*(6-6)+6=6
组合（92） 13333------1*(3-3)+3+3=6
组合（93） 13334------1+3+3+3-4=6
组合（94） 13335------1+(3-3)*3+5=6
组合（95） 13336------1*(3-3)*3+6=6
组合（96） 13344------1*3+3+4-4=6
组合（97） 13345------1+(3-3)*4+5=6
组合（98） 13346------1*(3-3)*4+6=6
组合（99） 13355------1*3+3+5-5=6
组合（100）13356------1*(3-3)*5+6=6
组合（101）13366------1*(3-3)*6+6=6
组合（102）13444------(-1+3+4)+4-4=6
组合（103）13445------1+3*(4-4)+5=6
组合（104）13446------1*3*(4-4)+6=6
组合（105）13455------(-1+3+4)+5-5=6
组合（106）13456------(1+3-4)*5+6=6
组合（107）13466------(-1+3+4)+6-6=6
组合（108）13555------1+3*(5-5)+5=6
组合（109）13556------1*3*(5-5)+6=6
组合（110）13566------(-1+3+5)-6/6=6
组合（111）13666------1*3*(6-6)+6=6
组合（112）14444------1*(4+4)/4+4=6
组合（113）14445------1+4*(4-4)+5=6
组合（114）14446------1*4*(4-4)+6=6
组合（115）14455------1+(4-4)*5+5=6
组合（116）14456------1*(4-4)*5+6=6
组合（117）14466------1*(4-4)*6+6=6
组合（118）14555------1+4*(5-5)+5=6
组合（119）14556------1*4*(5-5)+6=6
组合（120）14566------(1+4-5)*6+6=6
组合（121）14666------1*4*(6-6)+6=6
组合（122）15555------1+5*(5-5)+5=6
组合（123）15556------1*5*(5-5)+6=6
组合（124）15566------1*(5-5)*6+6=6
组合（125）15666------1*5*(6-6)+6=6
组合（126）16666------1*6*(6-6)+6=6
组合（127）22222------2+2+2+2-2=6
组合（128）22223------2*(2-2)+2*3=6
组合（129）22224------2*(2-2)+2+4=6
组合（130）22225------(2+2)/(2+2)+5=6
组合（131）22226------2*(2-2)*2+6=6
组合（132）22233------2*(2-2)+3+3=6
组合（133）22234------2+(2-2)*3+4=6
组合（134）22235------2*2*2+3-5=6
组合（135）22236------2*(2-2)*3+6=6
组合（136）22244------2+(2-2)*4+4=6
组合（137）22245------(2+2+2)*(-4+5)=6
组合（138）22246------2*(2-2)*4+6=6
组合（139）22255------2+2+2+5-5=6
组合（140）22256------2*(2-2)*5+6=6
组合（141）22266------2*(2-2)*6+6=6
组合（142）22333------(2-2)*3+3+3=6
组合（143）22334------2+2+3+3-4=6
组合（144）22335------2/2*3/3+5=6
组合（145）22336------2-2+3-3+6=6
组合（146）22344------2*(4-4)+2*3=6
组合（147）22345------2+2+3+4-5=6
组合（148）22346------(2-2)*3*4+6=6
组合（149）22355------2*(5-5)+2*3=6
组合（150）22356------(2-2)*3*5+6=6
组合（151）22366------(2-2)*3*6+6=6
组合（152）22444------2+2*(4-4)+4=6
组合（153）22445------2/2*4/4+5=6
组合（154）22446------2-2+4-4+6=6
组合（155）22455------2*(5-5)+2+4=6
组合（156）22456------(2-2)*4*5+6=6
组合（157）22466------(2-2)*4*6+6=6
组合（158）22555------2-2+5+5/5=6
组合（159）22556------2-2+5-5+6=6
组合（160）22566------(2-2)*5*6+6=6
组合（161）22666------2-2+6-6+6=6
组合（162）23333------2*(3-3)+3+3=6
组合（163）23334------2+3*(3-3)+4=6
组合（164）23335------2+3+3+3-5=6
组合（165）23336------2*(3-3)*3+6=6
组合（166）23344------2+(3-3)*4+4=6
组合（167）23345------(2+4-5)*(3+3)=6
组合（168）23346------2*(3-3)*4+6=6
组合（169）23355------2*(5-5)+3+3=6
组合（170）23356------2*(3-3)*5+6=6
组合（171）23366------2*(3-3)*6+6=6
组合（172）23444------2+3*(4-4)+4=6
组合（173）23445------2*3+(4-4)*5=6
组合（174）23446------2*3*(4-4)+6=6
组合（175）23455------2*3+4*(5-5)=6
组合（176）23456------(2+3-5)*4+6=6
组合（177）23466------2*3+4*(6-6)=6
组合（178）23555------2*3+5*(5-5)=6
组合（179）23556------2*3*(5-5)+6=6
组合（180）23566------2*3+5*(6-6)=6
组合（181）23666------2*3+6*(6-6)=6
组合（182）24444------2+4*(4-4)+4=6
组合（183）24445------2+4+(4-4)*5=6
组合（184）24446------2*4*(4-4)+6=6
组合（185）24455------2+4+4*(5-5)=6
组合（186）24456------2*(4-4)*5+6=6
组合（187）24466------2*(4-4)*6+6=6
组合（188）24555------2+4+5*(5-5)=6
组合（189）24556------2+4+(5-5)*6=6
组合（190）24566------2+4+5*(6-6)=6
组合（191）24666------2+4+6*(6-6)=6
组合（192）25555------(2*5)/(5+5)+5=6
组合（193）25556------2*5*(5-5)+6=6
组合（194）25566------2*(5-5)*6+6=6
组合（195）25666------2*5*(6-6)+6=6
组合（196）26666------2*6*(6-6)+6=6
组合（197）33333------3+3+3*(3-3)=6
组合（198）33334------3+3+(3-3)*4=6
组合（199）33335------3+3+(3-3)*5=6
组合（200）33336------3+3+(3-3)*6=6
组合（201）33344------3+3+3*(4-4)=6
组合（202）33345------3-3-3+4+5=6
组合（203）33346------3*(3-3)*4+6=6
组合（204）33355------3+3+3*(5-5)=6
组合（205）33356------3*(3-3)*5+6=6
组合（206）33366------3*(3-3)*6+6=6
组合（207）33444------3+3+4*(4-4)=6
组合（208）33445------3+3+(4-4)*5=6
组合（209）33446------3+3+(4-4)*6=6
组合（210）33455------3+3+4*(5-5)=6
组合（211）33456------(3-3)*4*5+6=6
组合（212）33466------(3-3)*4*6+6=6
组合（213）33555------3+3+5*(5-5)=6
组合（214）33556------3-3+5-5+6=6
组合（215）33566------(3-3)*5*6+6=6
组合（216）33666------3-3+6-6+6=6
组合（217）34444------3*(4/4+4/4)=6
组合（218）34445------3*=6
组合（219）34446------3*4*(4-4)+6=6
组合（220）34455------3*(4/4+5/5)=6
组合（221）34456------3*(4-4)*5+6=6
组合（222）34466------3*(4-4)*6+6=6
组合（223）34555------3*=6
组合（224）34556------3*4*(5-5)+6=6
组合（225）34566------3*=6
组合（226）34666------3*4*(6-6)+6=6
组合（227）35555------3*(5/5+5/5)=6
组合（228）35556------3*5*(5-5)+6=6
组合（229）35566------3*(5-5)*6+6=6
组合（230）35666------3*5*(6-6)+6=6
组合（231）36666------3*6*(6-6)+6=6
组合（232）44444------4+(4/4+4/4)=6
组合（233）44445------(4+4)/(4+4)+5=6
组合（234）44446------4-4+4-4+6=6
组合（235）44455------4+(4/4+5/5)=6
组合（236）44456------4*(4-4)*5+6=6
组合（237）44466------4*(4-4)*6+6=6
组合（238）44555------(4/4)*(5/5)+5=6
组合（239）44556------4-4+5-5+6=6
组合（240）44566------(4-4)*5*6+6=6
组合（241）44666------4-4+6-6+6=6
组合（242）45555------4+(5/5+5/5)=6
组合（243）45556------4*5*(5-5)+6=6
组合（244）45566------4*(5-5)*6+6=6
组合（245）45666------4*5*(6-6)+6=6
组合（246）46666------4*6*(6-6)+6=6
组合（247）55555------(5+5)/(5+5)+5=6
组合（248）55556------5-5+5-5+6=6
组合（249）55566------5*(5-5)*6+6=6
组合（250）55666------5-5+6-6+6=6
组合（251）56666------5*(6-6)*6+6=6
组合（252）66666------6-6+6-6+6=6 按公式f(+,×;n)=2^b·3^a, (n=3a+2b, b=0,1,2) 可得
`b=0`时，`f(+,×;n)= 3^{n/3}`
`b=1`时，`f(+,×;n)=2·3^{(n-2)/3}\approx0.9615\cdot3^{n/3}`
`b=2`时，`f(+,×;n)=4·3^{(n-4)/3}\approx0.92448\cdot3^{n/3}`
综合以上3式可知，`0.92448\cdot3^{n/3}< f(+,×;n)\le 3^{n/3}`
我们可以转而考虑更一般的问题。对于一个正整数 n, 探查一个函数 g(n), 使得 n 可表为任意 g(n)个较小正整数（1≤□≤n）的算术运算。考虑最小的g(n), 记为G(n).
我不认为G(n)会与f(+,×;n)的反函数有关联，以f(+,×;n)来做下限猜想显得无厘头。 本帖最后由 aimisiyou 于 2015-10-12 13:51 编辑
想起以前玩纸牌游戏24点(除大小王外的四张牌(J代表11,Q代表12,K代表13),通过加减乘除得到24)!有些情况下是没有解的.那么最少要几张牌,通过加减乘除括号优先必然会得到24? aimisiyou 发表于 2015-10-12 13:48
想起以前玩纸牌游戏24点(除大小王外的四张牌(J代表11,Q代表12,K代表13),通过加减乘除得到24)!有些情况下是 ...
7张，这个我研究过 以下是n<10时，n个1通过加减乘除和括号优先计算所能得到的所有正整数
n 所能得到数
1----( 1 )
2----( 1、2 )
3----( 1、2、3 )
4----( 1、2、3、4 )
5----( 1、2、3、4、5、6 )
6----( 1、2、3、4、5、6、7、8、9 )
7----( 1、2、3、4、5、6、7、8、9、10、12 )----空缺11
8----( 1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、18 )----空缺17
9----( 1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、24、27 )----空缺22、23、25、26
空缺的应该是标准分解式比较短的一些数，具体规律比较难把握。 最近在做一个关于24点的东西，看到这个问题感觉挺有意思的。不过这个问题想要解决感觉难度不小。
解决方法一般就是找反例或者证明成立，分别帮楼主找点思路吧。
找反例的思路：
按照24点的规律，一般来说当几个参与计算的数字非常接近（多个重复）的时候更容易出现无解的情况。比如6个1-13之间的数字算24无解的组合是：
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3
1 1 1 1 2 2
1 10 10 10 10 10
9 9 9 9 9 9
9 9 9 9 9 10
9 9 9 10 10 10
9 9 10 10 10 10
10 10 10 10 10 10
共同规律就是相同（或相差1）的数字多，很大的原因是这类数字组合能构成的（非等效）表达式数量远远少于"3 6 8 9 10 12"这类组合。所以找反例可以从n个相同的数字上着手。而这个相同数字的不同选择也会有不同效果。比如6个9或6个10对24无解，7个17对24依然无解。也就是说对目标数24来说9和10附近以及17附近比较容易出现无解的组合。
现在回到楼主的问题上，选n = 11，f(+,×;11) = 54
我用程序跑了一下11个1至11个54这54组数对{0, 1, 2..., 54}这55个目标数分别的解的个数。（等效表达式去重不是很完美，但是数量级上看应该不会有问题）
第k行表示了11个k对0-54分别的解的个数。(图上只是一部分)
对结果加1再取对数就是下图。越偏绿色解的数量越多，越偏红了解越少。
可以看出：
1. 除了11个1以外其他每组数对0-54的每个目标数都有解。
2. 选的数在44左右的时候解的数量会偏少。
所以找反例的时候可以着重尝试在目标数80%左右的数字。
比如算81的时候选类似"63 63 63 63 63 63 63 62 62"这样的组合，在目标数80%左右，自身因数不多，前后相差不超过1。（这个例子确实是无解的，不过只有9个数字）
困难：
按照以往的经验看，当n比较小的时候很难存在反例。但当n达到15左右的时候，即使所有数字都一样，验证一个反例也需要相当长的时间。（时间复杂度至少是阶乘级的）
正向证明的思路：
直接证明的话可以考虑把问题先稍微一般化一下。
通过上面的试验结果可以看出，除了11个1以外其他每组数对0-54的每个目标数都有解，事实上"1 1 1 1 1 1 1 1 1 1 2"就已经对0-54都有解了。
所以可以考虑把假设一般化为：
所有能由n个1表示的正整数都能表示为任意n个不大于f(+,×;11)的正整数的四则运算。
或者
所有不大于f(+,×;11)的正整数都能表示为任意（除n个1外）n个不大于f(+,×;11)的正整数的四则运算。
然后可以尝试用归纳法分类考虑。
不过总得来说还是很困难的，感觉比较可行的方法还是优化算法然后试着找反例。
另外如果楼主有比较好的等效表达式去重的算法希望可以讨论一下。 whbns 发表于 2016-4-16 08:20
最近在做一个关于24点的东西，看到这个问题感觉挺有意思的。不过这个问题想要解决感觉难度不小。
解决方法 ...
邀请你去看一下，我的另一篇关于猜想的帖子，《正整数的四则分解与堆垒》（我自己琢磨的，恳请大家帮忙论证），想要一定得到24，需要数量9个、数值在1到24之间的任意数 裴进兵 发表于 2016-4-16 23:54
邀请你去看一下，我的另一篇关于猜想的帖子，《正整数的四则分解与堆垒》（我自己琢磨的，恳请大家帮忙论 ...
根据猜想的叙述是这样的。不过问题是n稍微大一点，程序验证就要非常长的时间。 whbns 发表于 2016-4-16 08:20
最近在做一个关于24点的东西，看到这个问题感觉挺有意思的。不过这个问题想要解决感觉难度不小。
解决方法 ...
从{1,2,...,k}中可重复地取n个数，有S(n)=C(n+k-1,n)种组合
n=2,f(+,×;2)=2， S(2)=C(3,2)=3
n=3,f(+,×;3)=3， S(3)=C(5,3)=10
n=4,f(+,×;4)=4， S(4)=C(7,4)=35
n=5,f(+,×;5)=6， S(5)=C(10,5)=252
n=6,f(+,×;6)=9， S(6)=C(14,6)=3003
页:
[1]