Enigmatic Code

Programming Enigma Puzzles

Enigma 1213: Sum coincidence

From New Scientist #2369, 16th November 2002 [link]

I have a little numerical party trick. I ask my audience to choose 10 different whole numbers less than 100 and from those 10 I find two quite separate collections with the same sum. For example, if they chose:

2, 6, 11, 19, 29, 45, 67, 68, 71 and 98

then one of my possible choices would be to note that:

2 + 68 = 6 + 19 + 45
or that 2 + 6 + 11 = 19

I tried a simpler version of this trick with my young niece. I asked her to choose five different whole numbers less than 13, and again I knew that I would be able to find two separate collections with the same sum.

She then asked me if it worked for any five numbers less than 14, and so we tried a few. This time she managed to find a set of five different numbers less than 14 among which there were no two separate collections with the same sum.

She then took the lowest of the five numbers and tripled it, leaving the other four unchanged. She got another set of five different numbers less than 14 among which there were still no two separate collections with the same sum.

What was this last set of five numbers?

[enigma1213]

Advertisements

One response to “Enigma 1213: Sum coincidence

  1. Jim Randell 3 August 2015 at 9:43 am

    This Python program runs in 85ms

    from collections import defaultdict
    from enigma import irange, subsets, printf
    
    # record sets of M numbers, up to N
    (N, M) = (13, 5)
    
    ss = set()
    for ns in subsets(irange(1, N), min_size=M, max_size=M):
    
      # and record the subsets by sum
      d = defaultdict(list)
      for s in subsets(ns):
        d[sum(s)].append(s)
    
      if all(len(v) < 2 for v in d.values()):
        ss.add(ns)
        printf("[ns = {ns}]")
    
    # now find a candidate set where replacing min(s) with 3 * min(s) is also a set in ss
    for s in ss:
      n = 3 * s[0]
      if n > N: continue
      t = tuple(sorted(s[1:] + (n,)))
      if t in ss:
        printf("{s} -> {t}")
    

    Solution: The final set of 5 numbers is (6, 9, 11, 12, 13).

    In fact there are only two sets that have no subsets that sum to the same value. The other one is the starting set: (3, 6, 11, 12, 13).

    If we consider numbers up to 14 then there are 12 more sets (that obviously include 14).

    And these would give rise to two further solutions:

    (1, 6, 10, 12, 14) → (3, 6, 10, 12, 14)
    (3, 6, 10, 12, 14) → (6, 9, 10, 12, 14).

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: