projects

Project Euler Problem 68: The Magic 5-gon

August 3, 2020

I wanted to discuss this problem because the magic 5-gon is a genuinely fascinating construction with deep ties to discrete math and combinatorics. Here's the problem statement.

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, with each line adding to nine.

3-gon diagram

Working clockwise, starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. The above solution is described by: 4,3,2; 6,2,1; 5,1,3.

Number combinations

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

5-gon diagram

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

Solution

Immediately, we can identify a few details critical to finding the solution.

First, we read each segment linearly starting from each external node, going clockwise. Every number in the interior of the 5-gon appears in exactly two segments, so each interior number is repeated.

Because we need a 16-digit string, the number 10 cannot appear in the interior (if it did, it would repeat, giving us 17 digits). So 10 must be an external node only.

Additionally, the external node of the first chain must have the lowest value among all external nodes (to enforce a canonical starting point).

Finally, each 3-element chain must have the same sum — just like in the 3-gon example where 4+3+2 = 5+3+1 = 6+1+2 = 9.

Implementation

Python's itertools library makes generating all permutations straightforward:

def Problem68():
    num_list = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
    fivegon_list = list(permutations(num_list))

From there, we iterate over all permutations, check whether each satisfies our three constraints, and track the maximum valid 16-digit string:

    max_fivegon = 0
    for fivegon in fivegon_list:
        # Each linear clockwise segment must have the same sum
        sum = int(fivegon[0]) + int(fivegon[1]) + int(fivegon[2])
        if sum != int(fivegon[3]) + int(fivegon[2]) + int(fivegon[4]) or \
                sum != int(fivegon[5]) + int(fivegon[4]) + int(fivegon[6]) \
                or sum != int(fivegon[7]) + int(fivegon[6]) + int(fivegon[8]) \
                or sum != int(fivegon[9]) + int(fivegon[8]) + int(fivegon[1]):
            continue
        # fivegon[0] must be the lowest external node
        if int(fivegon[0]) >= int(fivegon[3]) or int(fivegon[0]) >= int(fivegon[5]) \
                or int(fivegon[0]) >= int(fivegon[7]) or int(fivegon[0]) >= int(fivegon[9]):
            continue
        # 10 must not appear in the interior (would make a 17-digit string)
        if fivegon[1] == '10' or fivegon[2] == '10' or fivegon[4] == '10' \
                or fivegon[6] == '10' or fivegon[8] == '10':
            continue

        curr_fivegon = fivegon[0] + fivegon[1] + fivegon[2] + fivegon[3] + fivegon[2] + fivegon[4] + \
                       fivegon[5] + fivegon[4] + fivegon[6] + fivegon[7] + fivegon[6] + fivegon[8] + \
                       fivegon[9] + fivegon[8] + fivegon[1]
        if int(curr_fivegon) > max_fivegon:
            max_fivegon = int(curr_fivegon)

Finally, print the result:

    print("The maximum 16-digit fivegon is " + str(max_fivegon))

The answer is 6531031914842725.

This problem is a good reminder that combinatorics problems often reward careful constraint analysis. By ruling out 10 from the interior and fixing the starting node before brute-forcing, the search space collapses to something very manageable. Project Euler has been one of the best ways I've found to build intuition for this kind of thinking.

← All posts