Enigmatic Code

Programming Enigma Puzzles

Enigma 302: The Grand Enigma

From New Scientist #1450, 4th April 1985 [link]

The Puzzlers’ Union has just finished electing a new Grand Enigma, as its union president is called. Hook, Line and Sinker were the three candidates. Each canvassed shamelessly, and each arrived at the count expecting to receive 79 votes. As the total possible number of votes cast was, in fact, precisely 100, each was in for a surprise.

The Puzzlers’ Union has eight branches, all of different sizes and none of less than three members. Each branch made whatever promises it saw fit and, indeed, cast its votes en bloc. But, you may rightly infer, not all branches voted as promised. One branch had rashly pledged itself to all three candidates and then voted for no one. Three branches were pledged to two candidates — a different two in each case — and resolved the dilemma by voting for a third. This manoeuvre benefited Hook most, Line next and Sinker least. One branch promised no one and voted for no one. The remaining three branches were pledged one to Hook, one to Line and one to Sinker; and these pledges were kept in the vote.

Precisely how many votes did each candidate actually receive?

In New Scientist #1454 the following correction to this puzzle was published (I’ve removed the statement of the solution):

Martin Hollis writes: “As set, the puzzle has several solutions. In the first paragraph, 100 should have been given not as the total number of votes cast, but as the total possible. […] My apologies to all.”

I have modified the puzzle above accordingly.

[enigma302]

Advertisements

2 responses to “Enigma 302: The Grand Enigma

  1. Jim Randell 13 August 2015 at 9:31 am

    This Python 3 program runs in 737ms.

    # the behaviours of the 8 branches are as follows:
    #
    #   1. pledge = H+L+S, vote = none
    #   2. pledge = L+S, vote = H
    #   3. pledge = H+S, vote = L
    #   4. pledge = H+L, vote = S
    #   5. pledge = none, vote = none
    #   6. pledge = H, vote = H
    #   7. pledge = L, vote = L
    #   8. pledge = S, vote = S
    #
    # and the votes for 2, 3, 4 are  H > L > S
    #
    # so each candidate received 4 pledges (totalling 79)
    # and each candidate got 2 block votes
    
    from itertools import combinations, permutations
    from enigma import irange, printf
    
    # decompose <t> into <n> different numbers not less than <m>
    def decompose(t, n, m, s):
      if n == 1:
        if not(t < m):
          yield s + [t]
      else:
        for x in irange(m, t // n):
          yield from decompose(t - x, n - 1, x + 1, s + [x])
    
    # determine the make up of the branches
    for bs in decompose(100, 8, 3, []):
    
      # for the pledges we need to find subsets of size 4 that total 79
      ps = list(p for p in combinations(bs, 4) if sum(p) == 79)
      if len(ps) < 3: continue
    
      # choose 3 pledges for H, L, S
      for (pH, pL, pS) in permutations(ps, 3):
        (pH, pL, pS) = (set(pH), set(pL), set(pS))
    
        # b1 pledged to all
        b1s = pH.intersection(pL, pS)
        if len(b1s) != 1: continue
    
        # b2 pledged to L and S
        b2s = (pL.intersection(pS)).difference(b1s)
        if len(b2s) != 1: continue
    
        # b3 pledges to H and S
        b3s = (pH.intersection(pS)).difference(b1s)
        if len(b3s) != 1: continue
    
        # b4 pledges to H and L
        b4s = (pH.intersection(pL)).difference(b1s)
        if len(b4s) != 1: continue
    
        (b1, b2, b3, b4) = map(sum, (b1s, b2s, b3s, b4s))
        if not(b2 > b3 > b4): continue
    
        # b6 pledges to H
        b6s = pH.difference(b1s, b3s, b4s)
        if len(b6s) != 1: continue
    
        # b7 pledges to L
        b7s = pL.difference(b1s, b2s, b4s)
        if len(b7s) != 1: continue
    
        # b8 pledges to S
        b8s = pS.difference(b1s, b2s, b3s)
        if len(b8s) != 1: continue
    
        (b6, b7, b8) = map(sum, (b6s, b7s, b8s))
    
        # so the votes are
        (H, L, S) = (b2 + b6, b3 + b7, b4 + b8)
    
        printf("H={H} L={L} S={S} / bs={bs} / pH={pH} pL={pL} pS={pS} / b1={b1} b2={b2} b3={b3} b4={b4} b6={b6} b7={b7} b8={b8}")
    

    Solution: Hook received 15 votes. Line received 13 votes. Sinker received 11 votes.

    There is only one decomposition of 100 into 8 distinct numbers greater than 2 that has at least 3 subsets of size 4 that sum to 79. That is:

    100 = 3 + 4 + 5 + 6 + 7 + 8 + 9 + 58.

    The subsets of size 4 that sum to 79 are:

    4 + 8 + 9 + 58 = 79
    5 + 7 + 9 + 58 = 79
    6 + 7 + 8 + 58 = 79

    As there are only three such subsets, each of these corresponds to the pledges for one of Hook, Line and Sinker.

    We see that the branch that pledged itself to each candidate, but voted for none is the branch of size 58.

    And we see that the branches that pledged to two candidates are the branches of size 9, 8 and 7. So each of these voted for the candidate that they did not pledge to. Hook receiving the most votes, then Line then Sinker.

    So the branch of size 9 voted for Hook, the branch of size 8 for Line, and the branch of size 7 for Sinker. So in the list of subsets above the first gives the pledges for Sinker, the second is the pledges for Line and the last one is the pledges for Hook.

    The remaining branches – of size 4, 5, and 6 – kept their promises. So the branch of size 4 pledged for Sinker and voted for Sinker, so Sinker received 4 + 7 = 11 votes in total. The branch of size 5 pledged for Line and voted for Line. Line received 5 + 8 = 13 votes in total. The branch of size 6 pledged for Hook and voted for Hook. Hook received 6 + 9 = 15 votes in total.

    The branch of size 3 is the one that pledged to no-one and voted for no-one.

  2. Brian Gladman 14 August 2015 at 8:37 am
    from itertools import permutations
    
    # partition x into n parts with a minimum part of 3, returning
    # partitions in decreasing order 
    def part(x, n, p=[]):
      if n == 1:
        if x > p[0]:
          yield [x] + p
      else:
        for i in range(3, x + 1):
          if not p or i > p[-1]:
            yield from part(x - i, n - 1, [i] + p)
    
    # Label branches with their number of members so that: n1 pledges to all but
    # votes for none;  n2, n3 and n4 pledge to two but vote for one;  n5, n6, n7
    # are those that pledge and vote accordingly; and n8 doesn't vote or pledge. 
    # So we have:
    #
    #   pledges:         3.n1 + 2.(n2 + n3 + n4) + (n5 + n6 + n7) = 237
    #   possible votes:    n1 +   (n2 + n3 + n4) + (n5 + n6 + n7) + n8 = 100
    #
    # We can hence show that:
    #
    #   n1 = 137 + n8 - (n1 + n2 + n3 + n4)
    #
    # and hence:
    #
    #   min(n1) = 137 + min(n8) - max(n1 + n2 + n3 + n4) = 137 + 3 - 82 = 58
    #
    # But the maximum value for any branch is 100 - 42 (42 is the minimum sum for
    # seven branches), which is also 58, so we know that n1 = 58.
    n1 = 58
    
    # Since n1 + n8 = 100 - sum(n2 .. n7), max(n8) = 100 - n1 - 33 = 9 
    for n8 in range(3, 10):
        # choose n2, n3 and n4 by partitioning their sum (n2 > n3 > n4)
        for n2, n3, n4 in part(137 + n8 - 2 * n1, 3):
          # since Hook > Line > Sinker, (n2, n3, n4) -> (Hook, Line, Sinker)
          s5 = set([n1, n2, n3, n4, n8])
          other3 = 100 - sum(s5)
          if other3 >= 12:
            # partition the remainder for n5, n6 and n7
            for n567 in part(other3, 3):
              #  ensure that the eight votes are all different 
              if len(s5.union(n567)) == 8:
                # n1 pledges 58 to all, n2, n3 and n4 give pledges n3 + n4,
                # n4 + n2 and n2 + n3 respectively 
                pl234 = n3 + n4, n4 + n2, n2 + n3
                # find an order for the votes n5, n6 and n7 such that Hook,
                # Line and Sinker each obtain 75 pledges 
                for v567 in permutations(n567):
                  if all(n1 + x + y == 79 for x, y in zip(pl234, v567)):
                    votes = (x + y for x, y in zip((n2, n3, n4), v567))
                    print('Hook {}, Line {} and Sinker {}.'.format(*votes))
    

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: