问题
请看下面的“神奇”三角环，里面填上1至6，每条线的数字之和都为9：
在这个三角环的最外的节点中选取最小的节点，然后顺时针列出节点所在的线的所有节点的值（例如4、3、2），当三角环填入的数字的解（顺序）不一样、列出来的一串数字都会不一样。例如，上图的解就可以用这串数字表示：4,3,2;6,2,1;5,1,3。
实际上，每边数字之和可以有4种不同的情况：9、10、11和12。总共有8种解：
| 每边之和 | 解集 |
|---|---|
| 9 | 4,2,3; 5,3,1; 6,1,2 |
| 9 | 4,3,2; 6,2,1; 5,1,3 |
| 10 | 2,3,5; 4,5,1; 6,1,3 |
| 10 | 2,5,3; 6,3,1; 4,1,5 |
| 11 | 1,4,6; 3,6,2; 5,2,4 |
| 11 | 1,6,4; 5,4,2; 3,2,6 |
| 12 | 1,5,6; 2,6,4; 3,4,5 |
| 12 | 1,6,5; 3,5,4; 2,4,6 |
每组解的数字可链接成一个9位数；其中三角环中最大的这个9位数为432621513。
在下面的五角环中可以填入1至10，在不同的排列情况下对应的解链接而成的数字有可能是一个16或17位数字。请问这个五角环的解链接而成的最大的16位数是多少？
* 传送门
分析
先看三角环的情况。如果任意地排列，实际上是有\(6!=720\)种排列。而题目写明，实际上最多只有8种解。题目并没有强调要维持三角环的每边之和都相同的要求，实际上是要维持这个要求才可以继续做这个题目的。当每边之和为9，那么三角环的三边之和肯定是\(3\cdot9=27\)；而观察三边之和的计算过程，我们可以看到内环节点都会被相加两次，外环节点则只会被相加一次，例如:
\(\begin{aligned}
3\cdot9 &=27 \\
&=(4+3+2)+(6+2+1)+(5+1+3) \\
&=2\cdot(3+2+1)+(4+6+5)
\end{aligned}\)
而不论是三角环还是五角环，每条“边”都只有3个节点，而这3个节点当中，有2个是内环节点、1个是外环节点。也就是说，当我们确定了每条边的和的情况下，只要安排好内环、外环节点分别是什么，就可以求得一个环的解。
继续观察五角环的情况。如果我们暴力解题，10个数字任意排列，将有\(10!=3628800\)种可能。但是只要简单分析，这条题目就会变得极其简单。
题目提到解的链接数字有可能是16或者17位数，而题目只要求我们求最大的16位数。由于1至10只有10是2位数，也只有10出现在内环的情况下会在链接数字中出现2次、解的链接数字会是17位；这也意味着，题目的答案的解，10在外环上。
当10在外环上，我们按照题目顺时针读取解的每条边，第1条边的第1个数字肯定不会是10。首先因为10已经是外环上最大的数字、和题目要求的从『最外的节点中选取最小的节点』开始不符；其次是因为，就算允许从10开始读取，解的16位链接数字势必以“10xxx…”开头，肯定不会是解的链接数字最大的16位数。10在外环上无形中还限制了，外环相邻数字的跨度不可能超过1；如果有跨度大于1的情况，那么外环最小节点将会很小、甚至有可能是1，这也和题目要求要找最大的16位数相矛盾。这也意味着，答案的解的外环肯定是6,7,8,9,10、而内环则是1,2,3,4,5。
内外环数字确定下来后，5边的总和就肯定是\(2\cdot(1+2+3+4+5)+(6+7+8+9+10)=70\)，也就是说，每条边之和为70/5=14。
我们可以从外环节点6开始构造解，和它共边的内环2个节点要和为8才可以满足要求。由于每次数字在环上都只出现一次，所以不可能是4,4、2,6；也不可能是1,7，因为7在外环上；那只能是3,5。由于要链接起来的数字最大，所以5肯定邻近6，所以第一条边的解为6,5,3;：
然后按顺时针继续。观察三角环的情况，实际上比外环值最小大1的节点在逆时针方向。所以外环最小节点顺时针方向的相邻节点实际上就是外环的最大节点，在五角环的情况下就是10。14-10-3=1，所以这条边的解为10,3,1;：
接下来的外环节点便是9，14-9-1=4，所以这条边的解为9,1,4;；
接下来的外环节点便是8，14-8-4=2，所以这条边的解为8,4,2;；
接下来的外环节点便是7，这已经是最后一个空格了，所以这条边的解为7,2,5：
这个问题对喜欢玩数独/填字游戏的人来说简直就是小菜一碟。
答案
6531031914842725
打赏作者
由 bruce 于 2020-06-8 19:06 更新