怪兽分裂

mathe

由于这个问题求解过程主要瓶颈在存储，使用尽量小的存储空间保存结果就会特别重要。
其中上面分析过程中的红色路径非常重要，由于路径上中间点已经有两个红色相邻点，于是，如果它还有蓝色相邻点，删除这个蓝色相邻点并不影响结果。很容易分析出，如果下一轮中这个蓝色点也被使用，那么必然会产生一个红色三角形。由此，我们知道只需要保存红色路径以及两个端点相邻的蓝色点即可。
而对于任何一条红色路径，其第一段方向我们可以任意指定，此后，每个下一段只能选择三个方向之一(共6个相邻点，不能退回出发点，也不能走到和出发点相邻的两个点，不然会形成红色三角形)，所以每段线段只需要使用-1，0，1三个数字之一来表示，所以n段线段的红色路径只需要使用3^(n-1)访问内整数来表示。如果为了兼顾效率，可以将每5段最多3^5=243用8比特表示。
然后路径两端点每个同样最多有三个候选蓝色点可选择0-2个。使用3+3=6比特就可以描述这部分信息。

王守恩

里面有一串数——{4, 6, 10, 19, 38, 80, 170, 366, 786, 1690, 3618, 7730, 16450, 34914, 73858, 155842, 327938, 688514, 1442306, 3015426, 6292482, 13108738, 27265026, 56626178,
117444610, 243275778, 503324674, 1040199682, 2147500034, 4429209602, 9126838274, 18790531074, 38654771202, 79456993282, 163208888322, 335007645698,...}
LinearRecurrence[{5, -6, -6, 16, -8}, {4, 6, 10, 19, 38}, 36]——好像可以这样。

iseemu2009

mathe 发表于 2025-4-11 10:23
做出了前999个层内状态图，其中每个蓝色点代表容量为1的点，红色点代表容量为2的点。
看上去，每个状态图 ...

请问 mathe         .tgz 这个文件用什么软件打开？

iseemu2009

iseemu2009 发表于 2025-4-11 20:59
请问 mathe         .tgz 这个文件用什么软件打开？

.out 格式用什么软件打开？

iseemu2009

看了压缩包的内容了，例子中的数字全对上了，应该解出这道题了。但推导思想太复杂了，要慢慢理解。

mathe

由于每次变换，至少需要选择所有红色点，而且变换后红色点数目最多改变1，
所以对于红色点数目为n的图，需要至少分裂n+(n-1)+...+1次。由此得出这些图只有在可用分裂次数不小于\(\frac{(n+1)n}2\)才非0.
这样，就可以少计算很多数了，最终可以计算更大范围的结果了。
monster3.tgz (53.36 KB, 下载次数: 3)

7 天前 上传

点击文件名下载附件

，这次计算到前624项

王守恩

Floor[LinearRecurrence[{3, 4, -(17/3), -10, -(31/3), 21}, {1, 3, 9, 30, 99, 336}, 624]]——只是看首位数,这个也可以。

mathe

上图是典型一层中容量分布图。
上面L层三角形各点面积坐标(x,y,z)均满足x+y+z=L
而我们可以设左下角点坐标为(L,0,0), 右下角角(0,L,0)，顶上点坐标为(0,0,L)。
于是我们知道点(x,y,z)中哪个分量的值越大，越接近于对应的顶点。而某个坐标值相等的两个点在一条对应的线上，而且如果这是另外两个坐标绝对值差值都是1，那么它们相邻。
所以L层点(x,y,z)分裂出L+1层的点(x+1,y,z),(x,y+1,z), (x,y,z+1)正好构成一个小三角形，而且根据坐标分量越大离对应顶点越近的性质，这是L+1层一个尖角向上的小三角形。
从这个角度来看，上面分裂构成构成了L+1层尖角向上的小三角形和L层中顶点之间的一个一一映射关系。
另外如果选择L层两个相邻顶点，比如(x,y,z), (x+1,y-1,z), 它们都分裂出了L+1层的点(x+1,y,z), 所以可以得出L层两个点相邻的充要条件是它们在L+1层中对应小三角形有公共顶点。
由此，如果选择L+1层三个有一个公共顶点的尖角向上的小三角形，那么它们在L层中对应的三个点自然形成一个小三角形，而且容易看出这个小三角形尖角向下。
于是由此，我们将L+1层中这个三个尖角向上的小三角形的公共顶点可以一一映射到L层一个尖角向下的小三角形。也就是建立了L+1层每个点到L层尖角向下的小三角形之间的一一映射。

mathe

根据上面的分析，如上图一个L层的红色路径上点被全部分裂（蓝点都不分裂），那么生成L+1层容量图中，红点需要有两个下面一层的点分裂出它，对应L层图中一个尖角向下三角形，它有两个顶点是红点，可以看出，非常有意思，得到的红点路径正好是原图中红点路径中删除第一个点后平移了一点点位置。由于平移不改变图的性质，我们可以认为就是原路径删除掉第一个点的结果。对应递推式中项a62[n-7]
如果我们将最顶上蓝色点也分裂，可以得到结果图和原先L层的图一模一样（经验证连蓝色点都一样）。 对应递推式中项a128[n-8]
而如果我们将顶上偏右的蓝色点也分裂，那么得到图沿着红点遍历，需要走三个不同的方向，这个后面可以验证，存在三个不同方向的红点路径是不合法的，所以可以淘汰。
反之，如果我们分裂底下两个蓝点之一，会得到两种不同的合法分裂结果，红色路径长度和原先的相同，但是形状可能不同。对应递推式中a126[n-8]和a127[n-8]
当然还可以上面下面各分裂一个（但是类似前面说明，上面只能分裂最顶上一个，而不能分裂偏右那个），又可以得到两种红色路径长度更长的方案,对应递推式中a253[n-9]和a254[n-9].

mathe

现在解释为什么沿着红色点路径走不可以同时出现三种方向，如下图，如果存在三个方向，那么必然存在如下图中黄色圈出的部分，也就是连续三段它们方向不同。
可以知道经过一次分裂后到上面一层，还是保持三段的方向，但是中间一段长度减少了1. 所以最终经过若干层分裂后，中间一段长度会变成0，得到一个红色小三角形，这个是不合法的。

由此得到如果图中如果某个蓝点添加到红色路径后，会形成三种方向的，其实这个蓝点也可以提前删除，也就是上一楼帖子中，上面偏右的蓝点实际上总可以删除，不会影响结果。