algorithm - 欧拉计划 - 68

Question

我已经读过What is an "external node" of a "magic" 3-gon ring?我已经解决了 90 岁以前的问题，但是这个 n-gon 的事情让我很困惑，因为我根本不明白这个问题。

所以我拿着这个戒指，我知道外圈是 4、5、6，因为它们在内圈之外。现在他说有八种解决方案。下面列出的八种解决方案没有太多解释。让我来

9   4,2,3; 5,3,1; 6,1,2
9   4,3,2; 6,2,1; 5,1,3

那么我们如何得出这两个解决方案呢？我知道 4、3、2 是直线，6、2、1 是直线，5、1、3 是直线，它们是顺时针方向的，所以第二个解决方案是有意义的。

问题

1. 为什么第一个解4,2,3； 5,3,1; 6,1,2 逆时针走？不应该是 423 612 然后是 531 吗？
2. 我们如何得出 8 个解决方案。它只是随机选择三个数字吗？解决“N-gon”究竟意味着什么？

Answer 1

第一个不是逆时针方向。这是你从配置中得到的

        4
         \
          2
         / \
        1---3---5
       /
      6

顺时针方向，从外圈中的最小数字开始。

How do we arrive at 8 solutions. Is it just randomly picking three numbers? What exactly does it mean to solve a "N-gon"?

对于 N 边形，您有一个内部 N 边形，并且对于 N 边形的每一侧都有一个尖峰，例如

        X
        |
X---X---X
    |   |
    X---X---X
    |
    X

这样尖刺连​​同内N边的边连成一组三处。 N 边形的“解决方案”是一种配置，您可以在其中放置从 1 到 2*N 的数字，以便 N 组中的每组总和为相同的值。

尖刺末端的地方每组只出现一组，内部 N 边形的顶点上的地方分成两组。所以所有组的总和为

 N
 ∑ k +  ∑{ numbers on vertices }
k=1

内N边形顶点数之和至少为1 + 2 + ... + N = N*(N+1)/2 至多为(N+1) + (N+2) + ... + 2*N = N² + N*(N+1)/2 = N*(3*N+1)/2。

因此所有组的总和介于

N*(2*N+1) + N*(N+1)/2 = N*(5*N+3)/2

和

N*(2*N+1) + N*(3*N+1)/2 = N*(7*N+3)/2

包含，并且每组的总和必须介于

(5*N+3)/2

和

(7*N+3)/2

• 再次包容。

对于三角形 - N = 3 - 边界是 (5*3+3)/2 = 9 和 (7*3+3)/2 = 12。对于正方形 - N = 4 - 边界是 (5*4+3)/2 = 11.5 和 (7*4+3)/2 = 15.5 - 因为总和必须是整数，所以可能的总和是 12, 13, 14, 15。

回到三角形，如果每组的和是9，则和的和是27，顶点上的数的和一定是27 - (1+2+3+4 +5+6) = 27 - 21 = 6 = 1+2+3，所以顶点上的数字是 1、2 和 3。

要使总和为 9，连接 1 和 2 的一侧尖峰末端的值必须为 6，对于连接 1 和 3 的一侧，尖峰值必须为 5，连接一侧的尖峰值必须为 4 2 和 3。

如果您从尖峰上的最小值开始 - 4 - 您知道您必须将 2 和 3 放在尖峰突出的一侧的顶点上。有两种方法可以在那里排列两个数字，从而得出和 9 的两个解决方案。

如果每组的总和为10，则总和为30，顶点上的数字总和必须为9。要将9表示为从1到6的三个不同数字的总和，你有可能性

1 + 2 + 6
1 + 3 + 5
2 + 3 + 4

对于第一组，您有一侧连接 1 和 2，因此您需要在尖峰末端加一个 7 才能形成 10 - 无解。

对于第三组，两个数字的最小和是 5，但是 5+6 = 11 > 10，所以 6 没有位置 - 无解。

对于第二组，边的和是

1 + 3 = 4  -- 6 on the spike
1 + 5 = 6  -- 4 on the spike
3 + 5 = 8  -- 2 on the spike

并且你有两种方法来排列 3 和 5，这样组要么是 2-3-5 要么是 2-5-3，剩下的又是.

和数 11 和 12 的解可以类似地获得，或者通过将和数 9 的解中的 k 替换为 7-k 来获得。 10.

要解决问题，你现在必须找出

• 获取16位字符串或17位字符串是什么意思
• 当数字以规定的方式连接时，哪个组的总和会产生最大值。

(并使用铅笔和纸来获得最快的解决方案。)