greatscott

I wanted to discuss this problem because I thought the idea of the magic 5-gon is super fascinating. This problem has substantial tie-ins with discrete math, particularly with permutations. Here’s the text of the problem.

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

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

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

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 see a few details that will be critical to find the solution to this problem. First, we have to read the segments of digits linearly starting with each edge across the 5-gon. For example, in the 3-gon above, 4-3-2 is the first segment, while the last segment is 5-1-3. Not only do we read each segment across the shape, but the numbers within the body of the 5-gon must repeat. Moreover, each number within the 5-gon’s body will be present twice.

Because we know that the number must be 16 digits, that means we can be sure that the number 10 will not be present within the body of the 5-gon. In the 16-digit string, 1-9 makes 9 digits, plus 10 makes 11 digits total. That leaves 5 digits left to repeat in the body, meaning 10 cannot be present.

Additionally, the external node of the first chain must have the lowest value. For example, in the 3-gon above, 4 is less than 5, which is less than 6, so the 3-gon is valid. The 5-gon must meet the same standards.

Finally, each 3-digit chain must have the same sum. This is evident from the example provided above with the 3-gon; 4 + 2 + 3 = 5 + 3 + 1 = 6 + 1 + 2 = 9. Using these 3 details, we can easily find the maximum 16-digit string.

I found the solution for this problem in Python because the itertools library makes finding permutations incredibly easy. First, we can make a list of all of the permutations of a list containing strings of the numbers 1-10. This is very easy in Python:

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

After the list is generated, we can iterate over the list of permutations of the original list. We can predict which cells of the list will be repeated, and determine whether the placement of each number in the list allows for the list to meet the conditions listed above (1. each chain has the same sum, 2. 10 is not repeated, 3. The external node of the first chain must be the lowest).

We test for each of these conditions below; if a permutation meets these criteria, and if the 16-digit string is larger than the current integer stored in max_fivegon, the string will be converted to an integer and stored in max_fivegon.

max_fivegon = 0
    for fivegon in fivegon_list:
        # checks to see if all linear clockwise segments of the 5-gon 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
        # checks to see if fivegon[0] is 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
        # checks to see that 10 won't be repeated twice, allowing for a 16-digit sum
        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, the value of max_fivegon will print to the console, which ends up being 6531031914842725.

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

This problem was seriously interesting, and made me think more about practical applications to combinatorics. Project Euler’s been a huge part of my life this summer, and I hope you found this explanation useful!

Project Euler Problem 68

July 31st, 2020

Solution