068. 神奇五角形环(Magic 5-gon ring)

考虑下面这个神奇的三解形环,六个环中填了一至六六个数字,其中每一排相加都等于九:

img

按顺时针方向并且从最小的外部节点所在的一排开始(这里是4, 3, 2),每一个结果都是唯一的。比如,上面的图对应的结果是{4,3,2; 6,2,1; 5,1,3}。有八种可能的方式来完成上面这个三角形环,对应四个不同的总和:

img

把每个结果中的数字前后拼接起来可以形成一个九位数数字,最大的数字是432621513。使用数字一至十,根据排列的不同可以形成一个十六位数或者十七位数,那么一个五角形环可以形成的最大的十六位数是多少?

img

分析:这道题只要明白了题意,其实不需要编程就可以解决。根据题意,首先,我们要寻找一个数字,这个数字由一至十十个数字拼接而成,这十个数字会分成五个组,每个组由三个数字,这样总共有十五个数字,因为十是两位数,所以总共会有十六位数。其次,我们要寻找这个十六位数中的最大值,所以我们需要保证外层的五个节点比内层的五个节点要大,因此外层结点只应从{6,7,8,9,10}这五个数中选,内层五个节点从{1,2,3,4,5}五个数中选。因此这些数的和应该为\(6+7+8+9+10+2(1+2+3+4+50)=70\),因为分成五组且五组的值相等,因此每一组的值应该是\(70/5=14\)。根据这些原则,我们下面来做一些尝试:

按照题意,我们应该外层节点中的最小值开始,也就是从六开始,要让六和另外元素的和成为十四,则另外两个元素之和为八,则只有三和五两个元素满足要求,如下图:

img

接下来,为了让前后拼接形成的数字最大,我们按在剩下{10,9,8,7}从大到小的顺序顺时针填写外层数字。首先是十,因为内层数字已经有了一个三,那么剩下的数字只能填一,如下:

img

接来来我们在剩下三个外层节点中填上九、八、七,并要保证每一排三个数字的总和应该是十四,最后结果如下:

img

因此,很容易发现最终拼接形成的最大数字是6531031914842725,即为题目所求。