Project Euler 600
Project Euler 600
题目
Integer sided equiangular hexagons
Let \(H(n)\) be the number of distinct integer sided equiangular convex hexagons with perimeter not exceeding \(n\).
Hexagons are distinct if and only if they are not congruent.
You are given \(H(6)=1, H(12)=10, H(100)=31248\).
Find \(H(55106)\).
Equiangular hexagons with perimeter not exceeding \(12\)
解决方案
将六边形按顺时针记边长为\(x_1,x_2,x_3,x_4,x_5,x_6.\)等角意味着每条边的方向依次旋转 \(60^\circ\)。取平面中三条相隔 \(60^\circ\) 的单位方向向量 \(u,v,w\)，满足\(w=-(u+v).\)
则六条边向量可以写为\(x_1u,x_2v,x_3w,-x_4u,-x_5v,-x_6w.\)闭合条件是向量和为零：\((x_1-x_4)u+(x_2-x_5)v+(x_3-x_6)w=0.\)
代入 \(w=-(u+v)\) 得\(((x_1-x_4)-(x_3-x_6))u+((x_2-x_5)-(x_3-x_6))v=0.\)
因为 \(u,v\) 线性无关，上式等价于两系数同时为零，因此得到\(x_4-x_1=x_5-x_2=x_6-x_3.\)令这一公共差为 \(\delta\)，则存在等角六边形当且仅当\(x_4-x_1=x_5-x_2=x_6-x_3=\delta.\)
当边长均为正且按上述方向依次转动 \(60^\circ\) 时，得到的多边形是凸的；因此在计数时只需保证边长为正并满足该闭合条件即可。
把三对对边写成\((x_1,x_4),(x_2,x_5),(x_3,x_6),\)并用闭合条件\(x_4=x_1+\delta, x_5=x_2+\delta, x_6=x_3+\delta.\)注意如果把六边形整体旋转 \(180^\circ\)，三对对边会互换“长边/短边”的角色，等价于把 \(\delta\) 变号。为了避免重复，可约定\(\delta\ge 0,\)并令\(a=x_1, b=x_2, c=x_3,\)于是六条边长为\(a,b,c,a+\delta,b+\delta,c+\delta.\)
接下来对全等分类：旋转会在三条方向之间循环置换 \((a,b,c)\)，反射会改变顺序但不改变三者的多重集合，因此同一全等类只由 \(\delta\) 与 \({a,b,c}\) 决定。于是可再约定\(1\le a\le b\le c,\)从而每个全等类恰好对应一个四元组 \((a,b,c,\delta)\)。周长为\((a+a+\delta)+(b+b+\delta)+(c+c+\delta)=2a+2b+2c+3\delta.\)
因此
\[ H(n)=\left|\left\{(a,b,c,\delta)\in\mathbb Z_{\ge 0}:1\le a\le b\le c,2a+2b+2c+3\delta\le n\right\}\right|. \]
固定 \(\delta\)，令\(S=\left\lfloor\dfrac{n-3\delta}{2}\right\rfloor.\) 则需要计数\(f(S)=\left|\left\{(a,b,c): 1\le a\le b\le c,a+b+c\le S\right\}\right|.\)
由于最小周长为 \(2+2+2+3\delta=6+3\delta\)，所以\(0\le \delta\le \left\lfloor\dfrac{n-6}{3}\right\rfloor.\)于是
\[ H(n)=\sum_{\delta=0}^{\left\lfloor\frac{n-6}{3}\right\rfloor} f\left(\left\lfloor\frac{n-3\delta}{2}\right\rfloor\right). \]
定义\(g(x)=\left|\left\{(a,b,c): 1\le a\le b\le c,a+b+c=x\right\}\right|.\)则\(\displaystyle{f(S)=\sum_{x=1}^{S} g(x),}\)那么有前缀和 \(f(S)=f(S-1)+g(S)\)。
接下来推导 \(g(x)\) 的显式公，并按 \(x\bmod 6\) 分段。
由 \(1\le a\le b\le c\)，设\(b=a+u, c=b+v=a+u+v,\)其中 \(u,v\ge 0\)。代入和为\(a+b+c=3a+2u+v=x.\)
固定 \(a\) 后，\(u\) 可以取的整数范围由 \(v\ge 0\) 给出：\(v=x-3a-2u\ge 0\Longleftrightarrow0\le u\le \left\lfloor\dfrac{x-3a}{2}\right\rfloor.\)
所以对每个 \(a\) 的解数为 \(\left\lfloor\dfrac{x-3a}{2}\right\rfloor+1\)，并且 \(a\) 的范围为 \(1\le a\le \left\lfloor\dfrac{x}{3}\right\rfloor\)，因此\(\displaystyle{g(x)=\sum_{a=1}^{\left\lfloor x/3\right\rfloor}\left(\left\lfloor\frac{x-3a}{2}\right\rfloor+1\right).}\)
这个求和只依赖于 \(x\) 在模 \(6\) 下的余数（因为步长为 \(3\)，再除以 \(2\) 会引入二元奇偶结构），整理可得分段二次式：设 \(x=6k+r\)，其中 \(r\in\{0,1,2,3,4,5\}\)，则
\[\begin{aligned} g(6k)&=3k^2,\\ g(6k+1)&=3k^2+k,\\ g(6k+2)&=3k^2+2k,\\ g(6k+3)&=3k^2+3k+1,\\ g(6k+4)&=3k^2+4k+1,\\ g(6k+5)&=3k^2+5k+2.\\ \end{aligned} \]
于是对任意 \(K\ge 0\)，有\(\displaystyle{f(6K)=\sum_{x=1}^{6K} g(x)=\sum_{k=0}^{K-1}\sum_{r=1}^{5}g(6k+r)+\sum_{k=1}^{K}g(6k)=\sum_{k=0}^{K-1}(15k^2+15k+4)+\sum_{k=1}^{K}3k^2=\frac{K(12K^2+3K-1)}{2}.}\)
对 \(f(6K+r)\)（\(1\le r\le 5\)），直接在 \(f(6K)\) 的基础上补上余项，得到：
\[\begin{aligned} f(6K)&=\frac{K(12K^2+3K-1)}{2},\\ f(6K+1)&=\frac{K(12K^2+9K+1)}{2},\\ f(6K+2)&=\frac{K(12K^2+15K+5)}{2},\\ f(6K+3)&=6K^3+\frac{21}{2}K^2+\frac{11}{2}K+1,\\ f(6K+4)&=6K^3+\frac{27}{2}K^2+\frac{19}{2}K+2,\\ f(6K+5)&=6K^3+\frac{33}{2}K^2+\frac{29}{2}K+4.\\ \end{aligned}\]
类似的，通过对\(\delta\)模6进行分类讨论，最终得到：
\[\begin{aligned} H(6q)&=\left\lfloor\frac{3q^4+4q^3+4}{8}\right\rfloor,\\ H(6q+1)&=\left\lfloor\frac{3q^4+6q^3+q^2-2q+4}{8}\right\rfloor,\\ H(6q+2)&=\left\lfloor\frac{3q^4+8q^3+6q^2+4}{8}\right\rfloor,\\ H(6q+3)&=\left\lfloor\frac{3q^4+10q^3+9q^2+2q+4}{8}\right\rfloor,\\ H(6q+4)&=\left\lfloor\frac{3q^4+12q^3+16q^2+8q+4}{8}\right\rfloor,\\ H(6q+5)&=\left\lfloor\frac{3q^4+14q^3+21q^2+10q+4}{8}\right\rfloor. \end{aligned}\]
代码
1 | N = 55106 |