Enigmatic Code

Programming Enigma Puzzles

Enigma 1296: ET

From New Scientist #2454, 3rd July 2004

George drew an equilateral triangle, 3 units each side, divided into unit grid triangles, and asked his son how many triangles of all possible integer dimensions he could see in the diagram.

“Thirteen, Dad.”

“Correct,” said George, “I have now defined the ET function, which stands for Embedded Triangles.  For any positive integer the ET function is the number of equilateral triangles of all possible integer sizes and orientations which are formed by the grid lines in an equilateral triangle of the given length of side.  Hence ET(3) is 13.

George then drew several integer sided equilateral triangles of different sizes, each divided into unit grid triangles.

“Can you see anything interesting about these, son?”

“Yes, Dad. The ET function of the largest is the sum of the ET functions of the others.”

“Right again. And no smaller triangle can be the largest of such a group.”

What are the lengths of the sides of the triangles?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1296]

Advertisements

One response to “Enigma 1296: ET

  1. Jim Randell 5 September 2014 at 1:38 pm

    This Python program works by counting the triangles. It runs in 37ms.

    from itertools import count
    from enigma import T, irange, subsets, printf
    
    def ET(n):
      # consider upward pointing triangles
      u = sum(T(i) for i in irange(n, 1, step=-1))
      # and the downward pointing triangles
      d = sum(T(i) for i in irange(n - 1, 1, step=-2))
      return u + d
    
    # check ET[3]
    assert ET(3) == 13
    
    # map ET[i] -> i
    et = dict()
    for i in count(1):
      n = ET(i)
      printf("[ET[{i}] = {n}]")
    
      # consider subsets of ET's already found that sum to ET[i]
      ss = list(s for s in subsets(et.keys()) if sum(s) == n)
      if ss:
        for s in ss:
          printf("ET[{i}] = {n} = sum(ET{s})", s=list(et[x] for x in sorted(s)))
        break
    
      # record this number
      et[n] = i
    

    Solution: The triangles have sides of length 3, 4, 6 and 7.

    There is only one way to to pick the triangles for the case of ET[7] = 118.

    The next case happens at ET[10] = 315, and there are three sets of triangles that can be chosen:

    ET[10] = ET[4] + ET[7] + ET[8]
    ET[10] = ET[2] + ET[4] + ET[5] + ET[9]
    ET[10] = ET[1] + ET[2] + ET[3] + ET[5] + ET[6] + ET[8]

    The sequence ET[n] is A002717 in OEIS. [ http://oeis.org/A002717 ]

    So we could just use the following function to compute ET[n]:

    def ET(n):
      return n * (n + 2) * (2 * n + 1) // 8
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: