Magic_triangle

Since ${A_1, A_2, A_3, ..., A_{15}, A_{16}}$ is a permutation of the set ${1, 2, 3, ..., 15, 16}$ , that means $\displaystyle \sum_{n=1}^{16} A_n = 1 + 2 + 3 + ... + 15 + 16 = \frac{1}{2} \cdot 16 \cdot 17 = 136$ .

Adding all six of the given equations and simplifying gives $A_6 + A_7 + A_8 + A_{13} = 6S - 272$ .

From third given equation $A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = S$ and the fourth given equation $A_{5} + A_{6} + A_{7} + A_{8} + A_{9} = S$ , as well as $\displaystyle \sum_{n=1}^{16} A_n = 136$ , we obtain $A_1 + A_2 + A_3 + A_4 = 136 - 2S$ .

Similarly, $A_{5} + A_{10} + A_{11} + A_{12} = 136 - 2S$ and $A_{9} + A_{14} + A_{15} + A_{16} = 136 - 2S$ .

Let $B = A_{2} + A_{4} + A_{5} + A_{9} + A_{12} + A_{14}$ , $C = A_{1} + A_{3} + A_{10} + A_{11} + A_{15} + A_{16}$ , and $D = A_{6} + A_{8} + A_{13}$ .

From $A_6 + A_7 + A_8 + A_{13} = 6S - 272$ we get $D + A_7 = 6S - 272$ .

From $A_1 + A_2 + A_3 + A_4 = 136 - 2S$ , $A_{5} + A_{10} + A_{11} + A_{12} = 136 - 2S$ , and $A_{9} + A_{14} + A_{15} + A_{16} = 136 - 2S$ we get $B + C = 408 - 6S$ .

From $A_{1} + A_{2} + A_{3} + A_{5} + A_{6} + A_{10} + A_{11} = S$ , $A_{1} + A_{3} + A_{4} + A_{8} + A_{9} + A_{15} + A_{16} = S$ , and $A_{10} + A_{11} + A_{12} + A_{13} + A_{14} + A_{15} + A_{16} = S$ we get $B + 2C + D = 3S$ .

From $A_{2} + A_{6} + A_{7} + A_{13} + A_{14} = S$ , $A_{4} + A_{7} + A_{8} + A_{12} + A_{13} = S$ , and $A_{5} + A_{6} + A_{7} + A_{8} + A_{9} = S$ we get $B + 2D + 3A_7 = 3S$ .

Combining $D + A_7 = 6S - 272$ , $B + C = 408 - 6S$ , $B + 2C + D = 3S$ , and $B + 2D + 3A_7 = 3S$ we get $B = -A_7 - 9S + 544$ , $C = A_7 + 3S - 136$ , and $D = -A_7 + 6S - 272$ .

For $S \leq 49$ and $1 \leq A_7 \leq 16$ , $B \geq 87$ . However, the highest value that $B$ can be is $11 + 12 + 13 + 14 + 15 + 16 = 81$ . Therefore, $S \geq 50$ .

For $S \geq 56$ and $1 \leq A_7 \leq 16$ , $D \geq 48$ . However, the highest value that $D$ can be is $14 + 15 + 16 = 45$ . Therefore, $S \leq 55$ .

Armed with $50 \leq S \leq 55$ and the above equations, we can now use a computer program to brute force each possible number of magic triangles for chosen values of $S$ and $A_7$ . (Note: this still took over 16 hours on my computer to run!)

Ignoring symmetrical and rotational equal possibilities, the $S$ and $A_7$ values that give the maximum number of magic triangles is $S_{\text{max}} = 53$ and $A_{7\text{max}} = 16$ at $3088$ possible triangles. Therefore, $S_{\text{max}} + A_{7\text{max}} = 53 + 16 = \boxed{69}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

# Magic_triangle
# Python

from itertools import combinations
from itertools import permutations

# Function that finds the number of magic triangles
#   for chosen values of S and A7
def N(S, A7):
    count = 0
    # L1 is a list of numbers 1-16
    L1 = []
    for a in range(1, 17):
        L1.append(a)
    # L2 is a list of numbers 1-16 except A7
    L2 = []
    for a in range(1, 17):
        if a <> A7:
            L2.append(a)
    # C is a list of 2 number combinations
    #   from L2 for A6 and A8 (in order)
    C = list(combinations(L2, 2))
    # Go through all possibilities for chosen
    #   values of S, A7, A6, and A8
    for a in range(0, len(C)):
        A = []
        for c in range(0, 17):
            A.append(0)
        A[7] = A7
        A[6] = C[a][0]
        A[8] = C[a][1]
        A[13] = 6 * S - 272 - A[6] - A[8] - A[7]
        if A[13] > A[8]:
            # L3 is a list of numbers 1-16 except
            #   A7, A6, A8, and A13
            L3 = []
            for b in range(1, 17):
                if b <> A[6] and b <> A[7] and (
                    b <> A[8] and b <> A[13]):
                    L3.append(b)
            # P is a list of 6 number permutations
            #   from L3 for A2, A3, A9, A11, A12, and A15
            P = []
            P = list(permutations(L3, 6))
            for b in range(0, len(P)):
                A[2] = P[b][0]
                A[3] = P[b][1]
                A[9] = P[b][2]
                A[11] = P[b][3]
                A[12] = P[b][4]
                A[15] = P[b][5]
                # Determine the other A values
                A[4] = S - A[7] - A[8] - A[12] - A[13]
                A[5] = S - A[6] - A[7] - A[8] - A[9]
                A[14] = S - A[2] - A[6] - A[7] - A[13]
                A[1] = 136 - 2 * S - A[2] - A[3] - A[4]
                A[10] = 136 - 2 * S - A[5] - A[11] - A[12]
                A[16] = 136 - 2 * S - A[9] - A[14] - A[15]
                # T is the list of A values in order
                T = []
                for c in range(0, 16):
                    T.append(A[c + 1])
                # if T has the same numbers as L1, then
                #   add one to the count
                if sorted(T) == L1:
                    count += 1
    return count

# Go through each possible S value for 50 <= S <= 55
#   with each possible A7 value using the N function
#   and record the maximum N(S, A7) as Nmax 
Nmax = 0
for S in range(50, 56):
    for A7 in range(0, 17):
        N1 = N(S, A7)
        if N1 > Nmax:
            Nmax = N1
            Smax = S
            A7max = A7

# Display the results
print(Smax, A7max, Nmax)