找回密码
 欢迎注册
查看: 659|回复: 28

[讨论] 怪兽分裂

[复制链接]
发表于 2025-3-31 13:01:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
      在一个三维坐标网格中,位于格点 (x, y, z) 的一只怪兽,在目标格点 (x+1, y, z), (x, y+1, z) 和 (x, y, z+1)都是空位的情况下,可以将自身分裂成三只怪兽占据它们,并且使 (x, y, z) 恢复空位。若三个目标点中任何一个被占位时它不能分裂。
      开始时只有一只怪兽位于原点 (0, 0, 0), 经过 n 次分裂之后(任何 1 只发生分裂就记为 1 次),格阵中将会分布有 2n+1 只怪兽, 对应一个 2n+1 点的占位点集。记 `S_n` 为经过 n 次分裂后所有可能的占位点集之集,记D(n)=|`S_n`|。
      例1、`S_1`={{(1,0,0), (0,1,0), (0,0,1)}},   D(1)=1.
      例2、`S_2`={{(0,1,0), (0,0,1), (2,0,0), (1,1,0), (1,0,1)},
                      {(1,0,0), (0,0,1), (1,1,0), (0,2,0), (0,1,1)},
                      {(1,0,0), (0,1,0), (1,0,1), (0,1,1), (0,0,2)}}
                D(2)=3.
       已知 D(10) =44499,D(20) =9204559704,而D (100) 的末尾九位是780166455,求D(1000) 的末尾九位。  
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-1 16:32:22 | 显示全部楼层
可以重新定义“次”而提出另外一个问题。假定每秒发生一次分裂,每次都有最多的怪兽同时发生分裂,规则如下:
1、当两只怪兽有一个公共目标点时,当前最多只能有其中一只发生分裂。
2、发生分裂的怪兽,恢复的空位可以立即被本秒发生的分裂占据。(快速规则)
2'、发生分裂的怪兽,恢复的空位只能被下一秒发生的分裂占据。(慢速规则)
记 a(n)、a'(n)分别为快速规则和慢速规则第 n 秒发生分裂的怪兽数,求这个序列。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-4-1 22:24:29 来自手机 | 显示全部楼层
问题加上计时规则后会变得更复杂了。到后面怪兽越来越多时,考虑哪些能分裂,哪些不能,很费脑力。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-2 00:43:04 | 显示全部楼层
可以先降到二维来研究。试了一下,快速规则似乎唯一性更好,慢速规则歧路多。

点评

估计最终状态集合和分裂点集合有关系,而分裂点集合构成一棵树  发表于 2025-4-2 07:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-4 07:44:01 | 显示全部楼层
为了方便起见,我们可以用X来代表坐标(x,y,z), L(X)=x+y+z代表这个坐标的层数。
对于怪兽分裂n次后获得的一个集合,我们可以将集合里面所有位置按层数从大到小排列,然后逆向分裂过程,对它们在进行反向合并.
由于层数l里面所有坐标位置构成一个正三角形,对于同一个层数中所有点,我总可以从正三角一个角的位置开始向另外一条边合并,这样,合并的方案是唯一。
对于一个合法的分裂结果,总是可以将最大层的所有坐标合并到次大层,唯一的问题是合并后,次大层中某些位置可能会存在多只怪兽。
然后我们继续按同样方式合并次大层,直到最后全部合并到(0,0,0)这一个点。
开始合并之前,每个坐标可以有怪兽也可以没有,构成一个函数S(X), 其中如果位置X有怪兽,S(X)=1,不然S(X)=0.
合并过程中,每个位置怪兽可以达到的最大数目为容量C(X).
而对于每次将(x+1,y,z),(x,y+1,z),(x,y,z+1)合并为(x,y,z)的操作,我们称为对X=(x,y,z)的一次合并操作, 整个过程中对X的合并次数记为分裂数F(X)。
于是很显然C(X)=F(X)+S(X)。
此外很显然我们可以得到\(C((x,y,z))=F((x-1,y,z))+F((x,y-1,z))+F((x,y,z-1))\). (其中如果某个参数小于0,对应F(.)为0)

我们首先需要说明的是,如果给定一个结束状态S(X),存在一个对应合并过程使得最终可以合并到一个点(0,0,0),那么必然存在一个合法的分裂过程,从(0,0,0)分裂到最终S(X)的状态。这个是因为合并过程就唯一确定C(X)和F(X),然后我们总是从(0,0,0)开始分裂,对于每次分裂出来的任意一个点X,如果已经使用过的X的分裂次数小于F(X),那么就深度优先先分裂X,这个深度优先规则总可以保证不会出现怪兽冲突问题,从而最终必然能够到达结束状态。

由此我们不需要去考虑分裂的顺序问题,而只需要考虑哪些最终状态S(X)或哪些C(X)和F(X)可以被达到。

首先如果对于三个格子(x+1,y,z),(x,y+1,z),(x,y,z+1)有\(C(x+1,y,z)\ge2,C(x,y+1,z)\ge 2, C(x,y,z+1)\ge 2\)那么必然有\(F(x+1,y,z)\ge 1, F(x,y+1,z)\ge 1, F(x,y,z+1)\ge 1\), 于是我们可以得到\(C(x+1,y+1,z)\ge F(x+1,y,z)+F(x,y+1,z)\ge 2, C(x+1,y,z+1)\ge 2, C(x,y+1,z+1)\ge 2\), 这样,我们就可以从x+y+z+1层中三个两两相邻各自的容量不小于2位置得出x+y+z+2层中三个两两相邻的各自容量不小于2的位置。由此这个递推过程必然能够无限进行下去,得出怪兽的分裂过程无法终止,所以不是一个合法过程,所以我们得出
引理1: 同一层三个两两相邻格子(x+1,y,z),(x,y+1,z),(x,y,z+1),必然有一格容量小于2.
类似可以有
引理1.1:同一层三个两两相邻格子(x+1,y,z),(x,y+1,z),(x,y,z+1),必然有一格分裂数为0.
同样如果某个各个格子(x,y,z)的分裂数不小于2,我们可以得出(x+1,y,z),(x,y+1,z),(x,y,z+1)的容量都不小于2,所以得出
引理2:任意一个格子X的分裂数F(X)只能是0或1.
于是所有格子的分裂过程构成一个有向无环图,每条边的权重都只能是1. (因为每个位置最多分裂一次),而对于分裂n次的情况,这个对应有向无环图正好n个点,我们需要计算这样的图的数目。而且还需要满足引理1,引理2以及上面的约束即\(F((x-1,y,z))+F((x,y-1,z))+F((x,y,z-1))-F((x,y,z))=0或1\), 也就是除了根节点,每个点都只有一个或两个父节点。而且如果一个点有两个父节点,那么它必然分裂(有三个孩子节点)。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2025-4-4 10:57:11 | 显示全部楼层
mathe 发表于 2025-4-4 07:44
为了方便起见,我们可以用X来代表坐标(x,y,z), L(X)=x+y+z代表这个坐标的层数。
对于怪兽分裂n次后获得的一 ...

这就像不限向上分枝的树干,道理是这个道理,计算起来还是颇费脑力的。你这个逆向推导过程是从任意一个第n层的分枝向主干行进的吧,事先要知道第n层有多少个枝干才行吧?但事先知道不是可能的。

点评

这只是用于数学推理,最终计算肯定还是从下向上动态规划进行吧。  发表于 2025-4-4 11:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-4 15:06:59 | 显示全部楼层
我们现在假设从某个第k层所有状态容量构成的集合C出发,再分裂n次,可以的方案数目为R(C,n)
于是我们要计算的就是R({(0,0,0)->1},n)
我们直到,这个方案数目实际上是平移翻转都保持不变。也就是如果某个C中,
平移性:如果所有取值非零元素的横坐标都大于某个a,我们可以将所有元素的x坐标减a,那么结果不会发生变换,类似对于y,z坐标也相同。
翻转性:如果每个取值非零元素的xy坐标都交换,那么结果也不会发生变化,类似可以交换其它的坐标。
显然R(ANY,0)=1,R({(0,0,0)->1},1)=1.
而且R({(0,0,0)->1},n)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
为了计算R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n), 我们需要穷举三个位置(1,0,0),(0,1,0),(0,0,1)的F函数,可以有
(1,0,0) (0,1,0) (0,0,1)结果
00 0 当n=0时取1,不然取0
1 0 0 取R({(2,0,0)->1,(1,1,0)->1,(1,0,1)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
01 0 取R({(1,1,0)->1,(0,2,0)->1,(0,1,1)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
00 1 取R({(1,0,1)->1,(0,1,1)->1,(0,0,2)->1},n-1)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
11 0 取R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
10 1 取R({(2,0,0)->1,(1,1,0)->1,(1,0,1)->2,(0,1,1)->1,(0,0,2)->1},n-1)=R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
0 1 1 取R({(1,1,0)->1,(0,2,0)->1,(0,1,1)->2,(1,0,1)->1,(0,0,2)->1},n-1)=R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
11 1 三角形全1非法,取0

由此得出R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n)=(n==0?1:0)+3R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)+3R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1).
我们我们需要使用计算机构建各集合的递推式
R({(0,0,0)->1},n)=R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)
R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n)=(n==0)+3R({(1,0,0)->1,(0,1,0)->1,(0,0,1)->1},n-1)+3R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n-1)
等等

而比如计算R({(2,0,0)->1,(1,1,0)->2,(1,0,1)->1,(0,2,0)->1,(0,1,1)->1},n)
由于C(1,1,0)=2, 我们只能选择F(1,1,0)=1,于是在穷举过程中,同样由于全1三角形的存在,可以裁剪掉很多不必要的选择。


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-9 16:11:04 | 显示全部楼层
monster2.zip (395.02 KB, 下载次数: 1)
根据上面分析方案可以得到如下递推式

a1[n]=+a0[n-0]+a2[n-1]
a2[n]=+a0[n-0]+a2[n-1]+a2[n-1]+a3[n-2]+a2[n-1]+a3[n-2]+a3[n-2]
a3[n]=+a2[n-1]+a3[n-2]+a3[n-2]+a3[n-2]+a4[n-3]+a3[n-2]+a5[n-3]+a4[n-3]
a4[n]=+a3[n-2]+a4[n-3]+a5[n-3]+a4[n-3]+a6[n-4]+a7[n-4]
a5[n]=+a3[n-2]+a5[n-3]+a4[n-3]+a4[n-3]+a8[n-4]+a5[n-3]+a9[n-4]+a8[n-4]
a6[n]=+a4[n-3]+a7[n-4]+a6[n-4]+a6[n-4]+a10[n-5]+a11[n-5]
a7[n]=+a5[n-3]+a8[n-4]+a9[n-4]+a7[n-4]+a12[n-5]+a13[n-5]
a8[n]=+a4[n-3]+a6[n-4]+a7[n-4]+a8[n-4]+a14[n-5]+a15[n-5]
a9[n]=+a5[n-3]+a9[n-4]+a8[n-4]+a8[n-4]+a16[n-5]+a17[n-5]+a9[n-4]+a18[n-5]+a16[n-5]
a10[n]=+a7[n-4]+a13[n-5]+a12[n-5]+a10[n-5]+a19[n-6]+a20[n-6]
a11[n]=+a6[n-4]+a11[n-5]+a10[n-5]+a11[n-5]+a21[n-6]+a22[n-6]
a12[n]=+a8[n-4]+a15[n-5]+a14[n-5]+a12[n-5]+a23[n-6]+a24[n-6]
a13[n]=+a9[n-4]+a16[n-5]+a18[n-5]+a13[n-5]+a25[n-6]+a26[n-6]
a14[n]=+a6[n-4]+a10[n-5]+a11[n-5]+a14[n-5]+a27[n-6]+a28[n-6]
a15[n]=+a7[n-4]+a12[n-5]+a13[n-5]+a15[n-5]+a29[n-6]+a30[n-6]
a16[n]=+a8[n-4]+a14[n-5]+a15[n-5]+a17[n-5]+a31[n-6]+a32[n-6]+a16[n-5]+a33[n-6]+a34[n-6]
a17[n]=
a18[n]=+a9[n-4]+a18[n-5]+a16[n-5]+a16[n-5]+a35[n-6]+a36[n-6]+a18[n-5]+a37[n-6]+a35[n-6]

其中已知a0是特殊标记,也就是a0[0]=1,而对于所有其它n,a0[n]=0, 而对于其它ai[x],在x<0时必然为0. 而我们目标是计算a1[n].
比如根据第一行就可以得出
a1[0]=a0[0]=1
a1[1]=a2[0]=a0[0]=1
a1[2]=a2[1]=a2[0]+a2[0]+a2[0]=3
a1[3]=a2[2]=3a2[1]+3a3[1]=3*3+3*(a2[0])=12
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2025-4-10 09:15:08 | 显示全部楼层
a1[100]=31022863355197733835084656754275104117019058780166455
a1[200]=4480030736794902002376087592907372109112923882248759630967814762646144183583161840359612734499382545262907
上面a1[3]弄错了,是3a2[1]+3a3[0]=9
monster3.zip (13.02 KB, 下载次数: 6)
附件中是1-299的数据,其中[]里面的是需要的集合数目

点评

不过内存增加速度太快了,大概没增加15项左右内存会翻倍,到300项左右就应该计算不下去了  发表于 2025-4-10 09:45
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 7 天前 | 显示全部楼层
gend.tgz (163.01 KB, 下载次数: 6)
做出了前999个层内状态图,其中每个蓝色点代表容量为1的点,红色点代表容量为2的点。
看上去,每个状态图都是连通的,而且除了a1/a2,所有图中红色点都连通形成一条路径,而蓝色点至少同一个红色点相邻,并且蓝色点数目总是比红色点多3.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-4-18 05:51 , Processed in 0.103099 second(s), 25 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表