原材料加工问题

wayne

ok， 我理解成 每次加工，体积减半之后，0级的材料自动补满了。

mathe

wayne的方法不错，去掉了添加0级原料的次数，可以给出本题一个上界，估计用这方法可以证明极限为0

wayne

额，mathe发话了，那我继续贴结果。
我这个方法很笨，时间是指数级别的增长。就是计算 每增加一次加工次数，对应的材料级别的体积分量比，取最大的一组。

1. {{1,3/2},{2,7/4},{3,17/8},{4,39/16},{5,87/32},{6,187/64},{7,413/128},{8,891/256},{9,1899/512},{10,4063/1024},{11,8681/2048},{12,18447/4096}}

复制代码

===
价值取最大的时候对应的体积分量比 也贴出来把（数组内部顺序是 按等级数增加而排列）：

1. {1,{{1/2,1/2}}}
   
2. {2,{{1/4,3/4,0},{3/4,0,1/4}}}
   
3. {3,{{5/8,0,3/8,0},{3/8,3/8,1/4,0}}}
   
4. {4,{{5/16,5/16,3/8,0,0}}}
   
5. {5,{{13/32,13/32,0,3/16,0,0}}}
   
6. {6,{{25/64,25/64,0,7/32,0,0,0},{13/64,39/64,0,3/16,0,0,0},{39/64,0,13/64,3/16,0,0,0},{25/64,25/64,0,7/32,0,0,0}}}
   
7. {7,{{47/128,47/128,0,17/64,0,0,0,0},{65/128,0,39/128,3/16,0,0,0,0},{39/128,39/128,13/64,3/16,0,0,0,0},{47/128,47/128,0,17/64,0,0,0,0}}}
   
8. {8,{{89/256,89/256,0,39/128,0,0,0,0,0},{65/256,65/256,39/128,3/16,0,0,0,0,0}}}
   
9. {9,{{217/512,217/512,0,0,39/256,0,0,0,0,0},{169/512,169/512,0,87/256,0,0,0,0,0,0},{145/512,145/512,87/256,0,3/32,0,0,0,0,0}}}
   
10. {10,{{555/1024,0,333/1024,0,17/128,0,0,0,0,0,0},{333/1024,333/1024,111/512,0,17/128,0,0,0,0,0,0},{555/1024,0,333/1024,0,17/128,0,0,0,0,0,0},{333/1024,333/1024,111/512,0,17/128,0,0,0,0,0,0}}}
    
11. {11,{{1085/2048,0,651/2048,0,39/256,0,0,0,0,0,0,0},{651/2048,651/2048,217/1024,0,39/256,0,0,0,0,0,0,0},{555/2048,555/2048,333/1024,0,17/128,0,0,0,0,0,0,0},{555/2048,555/2048,333/1024,0,17/128,0,0,0,0,0,0,0}}}
    
12. {12,{{1085/4096,1085/4096,651/2048,0,39/256,0,0,0,0,0,0,0,0}}}
    

复制代码

wayne

如果去掉添加0级材料的次数，即 时间的度量单位按照加工材料的次数来度量，可以观察得到，上限 是$O(1/t)$

wayne

Fans露面了，前面的都暂时忽略吧，现在我重新整理了一下思路---

在单位时间内，只存在两种操作，一个是引进0级材料，一个是加工某个等级的材料。
我们可以稍微列一下式子，发现，“加工某等级材料”这一操作不会改变价值总量， 只有“引进0级材料”才会增加价值总量。

于是第$n$次操作：
如果是引进0级材料，则所带来的价值增量$\Delta_n$就是第$n-1$次操作之后某一个等级(比如等级$i$) 的材料对应的价值分量$p(i,n-1)$的一半，即 ${p(i,n-1)}/2$。
如果是加工材料，则带来的价值增量$\Delta_n$为$0$

于是$s_n=1+\sum_{i=1}^n\Delta_i =1+1/2* \sum_{i=1}^np(k_i,i-1)$

mathe

我们可以简单达到\(O\left( \frac1{\log(n)} \right)\)的复杂度。
我们选择\((0,1)\)中实数\(x\),比如\(x=\frac12\)
然后对于整数\(k\),我们可以选择整数\(h\)使得\(\frac k{2^h}<1-x\)
然后每次我们都先将\(0\)级材料压缩\(h\)次，使得所有非零级材料体积不超过\((1-x)\),然后补充\(0\)级（至少\(x\)的量）
于是\(k\)次以上操作(共添加材料\(k\)次，压缩\(hk\)次),得到价值不低于\(kx\)
所以平均价值为\(\frac x{h+1}\)
当然，我们可以继续加强，每次不需要压缩\(h\)次，而是只要余下体积不超过\((1-x)\)即可，这样，各次压缩次数近似为\(\log(2),\log(3),\dots,\log(k)\)等
所以总共操作近似\(\log(k!)\),复杂度还是不变

wayne

按照操作次数来度量不太容易分析，我们还是按照引进0级材料的次数来度量吧。
假设，第k-1次引进0级材料与第k次引进0级材料之间，发生了m次材料加工的操作，则这m次材料加工的操作不会带来价值总量的增加，但会影响各个级别材料的分量比。
===
一般化的分析码公式有点复杂，我还是分析前三个案例吧：

1) 第1次引进0级材料与第2次引进0级材料之间，发生了m次材料加工的操作。
则第2次引进0级材料后，价值总量的增量 $\Delta s=(1-1/{2^m})*1$
$r = {1+\Delta s}/{1+\Delta t} ={1+(1-1/{2^m})}/{1+m+1}$
这个函数在$m>=1$内是单调递减的。
所以取$m=1, s=3/2,t=3,r=1/2$.
此时，仓库材料的等级分量比是{1/2,1/2}

2) 第2次引进0级材料与第3次引进0级材料之间，发生了m次材料加工的操作。
待加工的等级有0,1.将整数m拆分成两个非负整数之和,$m=a+b$，分别表示等级0，1所提升的等级。
则价值总量的增量 $\Delta s=(1-1/{2^a})*1/2+(1-1/{2^b})*1/2$
$r = {3/2+\Delta s}/{3+\Delta t} ={3/2+(1-1/{2^a})*1/2+(1-1/{2^b})*1/2}/{3+a+b+1}$
这个二元函数在a=0,b=1或者a=1,b=0处取得最大值。
所以取$m=a+b=1, s=7/4,t=5,r=7/20$.
此时，仓库材料的等级分量比是{3/4,0,1/4},{1/4,3/4}

3) 第3次引进0级材料与第4次引进0级材料之间，发生了m次材料加工的操作。
对于{1/4,3/4}：
待加工的等级有0,1.将整数m拆分成两个非负整数之和,$m=a+b$，分别表示等级0，1所提升的等级。
则价值总量的增量 $\Delta s=(1-1/{2^a})*1/4+(1-1/{2^b})*3/4$
$r = {7/4+\Delta s}/{5+\Delta t} ={7/4+(1-1/{2^a})*1/4+(1-1/{2^b})*3/4}/{5+a+b+1}$
这个二元函数在a=0,b=1处取得最大值。
所以取$m=a+b=1, s=17/8,t=7,r=17/56$.
此时，仓库材料的等级分量比是{5/8,0,3/8}

对于{3/4,0,1/4}：
待加工的等级有0,2。将整数m拆分成三个非负整数之和,$m=a+b$，分别表示等级0,2所提升的等级。
与上面同理。取$a=1,b=0,m=a+b=1, s=17/8,t=7,r=17/56$.
此时，仓库材料的等级分量比是{3/8,3/8,1/4}

KeyTo9_Fans

可以找到非$0$极限的操作序列。

我们用数字$0$表示引入$0$级，数字$1$表示将$0$级加工成$1$级，数字$2$表示将$1$级加工成$2$级，数字$3$表示将$2$级加工成$3$级，依次类推。

记操作序列

$A_1=0,1,2$，

$A_2=A_1,A_1,3,4$，

$A_3=A_2,A_2,5,6$，

$A_4=A_3,A_3,7,8$，

……

$A_n=A_{n-1},A_{n-1},2n-1,2n$。

那么当$n->\infty$时，操作序列$A_n$所得价值与序列长度之比的极限大于$0$。

证明如下。

首先讨论序列长度。

$A_1$的长度是$(5-2)$，

$A_2$的长度是$(5*2-2)$，

$A_3$的长度是$(5*2^2-2)$，

$A_4$的长度是$(5*2^3-2)$，

……

依次类推可得$A_n$的长度是$(5*2^{n-1}-2)$。

然后讨论价值。

$A_1$可得$1/4$体积的$2$级材料，价值是$1$；

$A_2$里有$2$个$A_1$，第$1$个$A_1$的价值是$1$，但占去了$1/4$的仓库，导致第$2$个$A_1$的价值只有$(1-1/4)$，总价值是$(2-1/4)$，全部都是$4$级材料；

$A_3$里有$2$个$A_2$，第$1$个$A_2$的价值是$(2-1/4)$，但占去了$(2-1/4)/16$的仓库，导致第$2$个$A_2$的价值只有$(2-1/4)*(1-(2-1/4)/16)$，总价值是$(2-1/4)*(2-(2-1/4)/16)$，全部都是$6$级材料；

$A_4$里有$2$个$A_3$，第$1$个$A_3$的价值是$(2-1/4)*(2-(2-1/4)/16)$，但占去了$((2-1/4)*(2-(2-1/4)/16))/64$的仓库，导致第$2$个$A_3$的价值只有$(2-1/4)*(2-(2-1/4)/16)*(1-((2-1/4)*(2-(2-1/4)/16))/64)$，总价值是$(2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64)$，全部都是$8$级材料；

$A_5$里有$2$个$A_4$，第$1$个$A_4$的价值是$(2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64)$，但占去了$((2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64))/256$的仓库，导致第$2$个$A_4$的价值只有$(2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64)*(1-((2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64))/256)$，总价值是$(2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64)*(2-((2-1/4)*(2-(2-1/4)/16)*(2-((2-1/4)*(2-(2-1/4)/16))/64))/256)$，全部都是$10$级材料；

依次类推，所得结论如下。

记$a_1=1$，$a_2=a_1*(2-a_1/2^2)$，$a_3=a_2*(2-a_2/2^4)$，$a_4=a_3*(2-a_3/2^6)$，$a_5=a_4*(2-a_4/2^8)$，……

那么$A_n$的价值是$a_n$，全部都是$2n$级材料。

取$n=100$，数值计算的结果是$a_n/(5*2^{n-1}-2)=0.1571627411...$，

取$n=10^8$，数值计算的结果依然是$a_n/(5*2^{n-1}-2)=0.1571627411...$，

由此可以相信极限大于$0$，准确值大约是$0.1571627411$，与$9$楼的猜测一致。

严格证明极限大于$0$应该不难，继续尝试中……

#####

记$b_2=2-1/4$，$b_3=(2-1/4)*(2-2/16)$，$b_4=(2-1/4)*(2-2/16)*(2-(2*2)/64)$，$b_5=(2-1/4)*(2-2/16)*(2-(2*2)/64)*(2-(2*2*2)/256)$，……

则有$a_2\geq b_2$，$a_3\geq b_3$，$a_4\geq b_4$，$a_5\geq b_5$，……

而$b_n/2^{n-1}=(1-1/8)*(1-1/16)*(1-1/32)*(1-1/64)*...>1-1/8-1/16-1/32-1/64-...=3/4$，

由此可得$a_n/2^{n-1}>3/4$，

所以$a_n/(5*2^{n-1}-2)>3/20=0.15$。

证毕。