Magic Triangles

The magic triangle problem is to place the numbers \(1, 2, 3, 4, 5,\) and \(6\) on the vertices and edges of a triangle such that the sum along each side of the triangle is the same. For instance,

../../_images/triangle.png

I was interested in a slight variation of this problem, find all magic triangles when the numbers on the edges and vertices can be chosen out of the set \(\{1,2,\ldots, 7\}\). (Of course, this can be generalized to larger sets of integers.)

To solve this by means of a python program I decided to represent a triangle as a list of integers. For instance, the triangle from figure above can be represented as the list [1, 5, 3, 4, 2, 6]. Thus, I start at the top and read out the integers in a clockwise way.

Find all magic triangles

I start with some basic imports.

from itertools import permutations

With the permutations functions it is easy to generate all possible permuations of a list. Recall, a triangle is represented as a list. A random triagle is then a random permutation of the list of integers that we use to generate the triangles.

The next function checks whether the sums along each of the sides are equal. If so, it returns true, otherwise it returns false.

def checkSum(triangle):
    return sum(triangle[:3]) == sum(triangle [2:5]) \
           == sum(triangle[4:])+ triangle[0]

Now the computation of the magic triangles is easy. First, generate all possible triangles. Then, store only the triangles that satisfy the ‘magic’ property.

solutions = set()
for triangle in permutations(range(1,8), 6):
    if checkSum(triangle): # true if triangle is magic
        solutions.add(triangle)
print len(solutions)
108

Clearly, there are 108 solutions. I don’t know whether there is a simple argument to see this.

Find the unique magic triangles

Some inspection of the solutions show that many magic triangles are copies of each other, in the sense that they can be obtained from a given triangle by means of cyclic permutations or reflections. To remove these copies I proceed as follows.

I need two helper functions. One function rotates a triangle one step clockwise. For instance, it shifts the triangle \([1,2,3,4,5,6]\) to \([6, 1, 2, 3, 4, 5]\).

def cycle(triangle):
    return  triangle[1:] + (triangle[0], )

The other function produces a refected triangle that is obtained by a reflection in the line through the top of the triangle.

def reflect(triangle):
    return (triangle[0],) + triangle[5:0:-1]

Now all copies can be obtained from a given triangle. Realize that a counter-clock wise shift can be obtained by reflecting first, and then a cycle shift. It is clear that from a given triangle five copies can be obtained. Thus, an equivalence class of triangle contains six elements.

unique = set()   # store all unique triangles
while len(solutions) > 0:
    triangle = solutions.pop()
    unique.add(triangle)
    for i in range(6):
        triangle = cycle(triangle)
        solutions.discard(triangle)
        solutions.discard(reflect(triangle))

print len(unique)

Now only 9 unique triangles remain.

Let’s consider an example:

for triangle in unique:
    if sum(triangle[:3]) == 10:
        print triangle
(1, 6, 3, 5, 2, 7)