原材料加工问题

KeyTo9_Fans

工厂的仓库体积为1：



在每个单位时间里，工厂可以引进一批原材料（等级为0），把仓库填满：



（如果仓库是满的，则无法进行此项操作。）

或者把某个等级的材料加工一次：



材料每加工一次，体积就会减半，等级提升1级。

等级为$n$的材料，每单位体积的价值为$2^n$。

假设该工厂只进行“引入原材料”和“加工某个等级的材料”这两项操作。

问：

是否存在一个操作序列使得$\lim_{t->\infty}s/t>0$？

其中$t$是时间，$s$是仓库中的材料的总价值。

如果存在，该极限值最大是多少？

KeyTo9_Fans

我把这道题做成了一个游戏。

下载附件解压后就可以玩了。

upgrade.rar (427.84 KB, 下载次数: 7)

2012-6-8 23:05 上传

点击文件名下载附件

点击空白处是“填满仓库”，点击非空白处是“加工”。

游戏的目标是用尽可能少的点击次数引进尽可能多的材料。

对于特定的$t$，它会自动记录最好成绩。

看谁玩的记录最好

KeyTo9_Fans

手工操作$t\leq 20$的情况，得到的$s/t$的值如下：

1: 1.0000000000000000
3: 0.5000000000000000
4: 0.4375000000000000
7: 0.3303571428571429
10: 0.2921875000000000
14: 0.2601841517857143
20: 0.2348358154296875

猜想：极限存在且大于$0$。

mathe

容易看出最优操作，每次要么补满，要么升级最低等级的材料。所以搜索到20步还是比较容易的

mathe

至于极限我猜测是零，只是很慢

mathe

估算变到0.01左右需要2＾200次左右的变换

KeyTo9_Fans

你是怎么操作的？

极限为什么是$O(1/\log t)$？

没有更好的方案了吗？

mathe

极限只是猜测，感觉各种不同方案在阶上不会有太大的区别

KeyTo9_Fans

手工操作$t\leq 2000$的情况，得到的$s/t$的值如下：

1: 1.0000000000000000
3: 0.5000000000000000
4: 0.4375000000000000
7: 0.3303571428571429
10: 0.2921875000000000
14: 0.2601841517857143
20: 0.2348358154296875
30: 0.2148714621861776
48: 0.1962810989883413
70: 0.1862673661399854
100: 0.1784434079112382
200: 0.1690430704761923
300: 0.1655674170990377
500: 0.1628229610442237
1000: 0.1603066762577333
2000: 0.1588870558059160

猜测极限为$0.157$左右。

wayne

我的理解是否有误， 我算了下前四次加工，算得每增加一次加工，对应的最大价值时间比是

1. {1,3/2=1.5}
   
2. {2,7/8=0.875}
   
3. {3,17/24=0.708333}
   
4. {4,39/64=0.609375}
   

复制代码

每一个等级材料对应的体积数的 所有可能情况有：

1. {1,{{1/2,1/2}}}
   
2. {2,{{1/4,3/4,0},{3/4,0,1/4}}}
   
3. {3,{{1/8,7/8,0,0},{5/8,0,3/8,0},{3/8,3/8,1/4,0},{7/8,0,0,1/8}}}
   
4. {4,{{1/16,15/16,0,0,0},{9/16,0,7/16,0,0},{5/16,5/16,3/8,0,0},{13/16,0,0,3/16,0},{3/16,9/16,1/4,0,0},{9/16,0,7/16,0,0},{1/2,3/8,0,1/8,0},{7/16,7/16,0,1/8,0},{15/16,0,0,0,1/16}}}
   

复制代码