Problem 68: Magic 5-gon Ring

Mathematical Analysis

Definition

A magic 5-gon ring is a graph consisting of 5 outer nodes $o_1, o_2, o_3, o_4, o_5$ and 5 inner nodes $i_1, i_2, i_3, i_4, i_5$ arranged as a pentagon, together with an assignment of the integers $\{1, 2, \ldots, 10\}$ (each used exactly once) such that all five lines share a common sum $S$:

The string representation is formed by reading the triples $(o_k, i_k, i_{(k \bmod 5)+1})$ clockwise, starting from the triple with the smallest outer node, and concatenating all digits.

Theorem 1 (Line Sum Constraint)

The common line sum satisfies $S = 11 + \frac{1}{5}\sum_{k=1}^{5} i_k$. In particular, $5 \mid \sum_{k=1}^{5} i_k$.

Proof. Summing all five line equations:

Since each of $1, \ldots, 10$ is used exactly once, $\sum o_k + \sum i_k = 55$, whence $\sum o_k = 55 - \sum i_k$. Substituting:

Since $S$ must be a positive integer, $5 \mid \sum_{k=1}^{5} i_k$. $\square$

Theorem 2 (16-Digit Necessity)

The string representation has exactly 16 digits if and only if the number 10 is assigned to an outer node.

Proof. Each outer node $o_k$ appears in exactly one triple, contributing $d(o_k)$ digits, where $d(x)$ denotes the number of decimal digits of $x$. Each inner node $i_k$ appears in exactly two triples, contributing $2 \cdot d(i_k)$ digits. The total digit count is:

For the numbers $1, \ldots, 9$, $d = 1$; for 10, $d = 2$.

• If 10 is outer: $D = 2 + 4 \cdot 1 + 2 \cdot 5 \cdot 1 = 16$.
• If 10 is inner: $D = 5 \cdot 1 + 2(2 + 4 \cdot 1) = 5 + 12 = 17$.

Hence $D = 16$ if and only if 10 occupies an outer node. $\square$

Theorem 3 (Optimal Partition)

Among all valid 16-digit magic 5-gon rings, the maximum string is achieved with inner nodes $\{1, 2, 3, 4, 5\}$ and outer nodes $\{6, 7, 8, 9, 10\}$, yielding line sum $S = 14$.

Proof. By Theorem 2, 10 must be outer. The inner node set $I \subset \{1, \ldots, 9\}$ has $|I| = 5$ and must satisfy $5 \mid \sum I$. We seek to maximize the string, which favors large values in the outer positions (since outer values appear in the leading positions of each triple).

We enumerate the feasible inner sums. We need $\sum I \equiv 0 \pmod{5}$ where $I \subset \{1,\ldots,9\}$, $|I| = 5$. The minimum possible sum of any 5-element subset is $1+2+3+4+5 = 15$. The possible sums divisible by 5 are $15, 20, 25, 30, 35$ (where 35 = $5+6+7+8+9$ is the maximum).

To maximize outer node values, we minimize the inner sum, choosing $I = \{1,2,3,4,5\}$ with $\sum I = 15$ and $S = 14$.

It remains to verify that a valid assignment exists for this partition and that no other partition yields a lexicographically larger 16-digit string. Since $\{6,7,8,9,10\}$ are the outer values and outer nodes lead each triple, this partition places the largest possible digits in the most significant positions. $\square$

Lemma (Outer Node Determination)

Given the inner permutation $(i_1, i_2, i_3, i_4, i_5)$ as a cyclic arrangement of $\{1,2,3,4,5\}$ and line sum $S = 14$, each outer node is uniquely determined by $o_k = 14 - i_k - i_{(k \bmod 5)+1}$. The arrangement is valid if and only if $(o_1, \ldots, o_5)$ is a permutation of $\{6,7,8,9,10\}$.

Proof. Immediate from the line equation $o_k + i_k + i_{(k \bmod 5)+1} = 14$. The outer values must be distinct elements of $\{6,7,8,9,10\}$ since each number is used exactly once. $\square$

Editorial

The analysis reduces the search to inner nodes $\{1,2,3,4,5\}$ and outer nodes $\{6,7,8,9,10\}$ with common line sum $14$. We therefore enumerate the cyclic order of the inner nodes, derive the outer nodes from the line-sum constraint, and discard any arrangement whose derived outer values are not exactly $\{6,7,8,9,10\}$. Every valid ring is normalized by starting at the smallest outer node, then read clockwise to form its 16-digit string; the largest such string is retained.

Pseudocode

Start with no best string.

For each cyclic arrangement of the inner nodes 1 through 5:
    derive the five outer nodes from the common-sum equation
    if the derived outer values are not exactly 6 through 10, discard the arrangement

    locate the smallest outer node
    from that position, read the five triples clockwise and concatenate them

    if the resulting 16-digit string is larger than the current best:
        replace the current best string

Return the largest string found.

Complexity

• Time: $O(5!) = O(1)$. Only 120 permutations to check.
• Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Magic 5-gon ring: inner = {1,2,3,4,5}, outer = {6,7,8,9,10}, S = 14.
    // Enumerate permutations of inner ring; outer[k] = 14 - inner[k] - inner[(k+1)%5].
    // Valid iff outer is a permutation of {6,7,8,9,10}.

    vector<int> inner = {1, 2, 3, 4, 5};
    string max_str = "";

    do {
        vector<int> outer(5);
        bool valid = true;
        set<int> outer_set;

        for (int k = 0; k < 5; k++) {
            outer[k] = 14 - inner[k] - inner[(k + 1) % 5];
            if (outer[k] < 6 || outer[k] > 10) { valid = false; break; }
            outer_set.insert(outer[k]);
        }

        if (!valid || outer_set.size() != 5) continue;

        // Start from the line with the smallest outer node
        int start = 0;
        for (int k = 1; k < 5; k++) {
            if (outer[k] < outer[start]) start = k;
        }

        string s = "";
        for (int k = 0; k < 5; k++) {
            int idx = (start + k) % 5;
            s += to_string(outer[idx]);
            s += to_string(inner[idx]);
            s += to_string(inner[(idx + 1) % 5]);
        }

        if (s.length() == 16 && s > max_str) {
            max_str = s;
        }

    } while (next_permutation(inner.begin(), inner.end()));

    cout << max_str << endl;

    return 0;
}

"""
Project Euler Problem 68: Magic 5-gon Ring

Find the maximum 16-digit string for a magic 5-gon ring using numbers 1-10.

By Theorem 2, 10 must be outer for a 16-digit string.
By Theorem 3, inner = {1,2,3,4,5}, outer = {6,7,8,9,10}, S = 14.
"""

from itertools import permutations


def main():
    max_str = ""

    for inner in permutations([1, 2, 3, 4, 5]):
        outer = []
        valid = True
        for k in range(5):
            o = 14 - inner[k] - inner[(k + 1) % 5]
            if o < 6 or o > 10:
                valid = False
                break
            outer.append(o)

        if not valid or sorted(outer) != [6, 7, 8, 9, 10]:
            continue

        start = outer.index(min(outer))

        s = ""
        for k in range(5):
            idx = (start + k) % 5
            s += str(outer[idx])
            s += str(inner[idx])
            s += str(inner[(idx + 1) % 5])

        if len(s) == 16 and s > max_str:
            max_str = s

    print(max_str)


if __name__ == "__main__":
    main()