Enigmatic Code

Programming Enigma Puzzles

Enigma 272: Squares and crosses

From New Scientist #1419, 30th August 1984 [link]

The Returning Officer was a terrible tease. After the votes had been counted he addressed the three candidates as follows: “By a strange coincidence each of you has polled a number of votes which is a perfect square. I have told each candidate separately how many votes he received — you all got some I am pleased to say. The winner got exactly 50 per cent of the votes cast. As you know the total electorate is 1000”. He then asked each candidate in turn if he could deduce the full result.

The Amity candidate said: “I cannot even deduce the percentage turnout”.

The Brotherhood candidate then said: “I know how many votes were cast for each candidate”.

The Comradeship candidate said: “So do I”.

The Amity candidate then said: “So do I now”.

The three candidates were of course perfect logicians and entirely honest.

How many votes did each receive?

[enigma272]

Advertisements

5 responses to “Enigma 272: Squares and crosses

  1. Jim Randell 11 April 2015 at 8:28 am

    This Python program uses the filter_unique() routine (see Enigma 265) now part of the enigma.py library. It runs in 43ms.

    from collections import namedtuple
    from itertools import combinations_with_replacement, permutations
    from enigma import irange, filter_unique, printf
    
    # squares less than 1000
    squares = set(i * i for i in irange(1, 31))
    
    # accumulate possible results as (A, B, C)
    Result = namedtuple('Result', 'A B C')
    results = set()
    
    # consider votes for the losing 2 candidates
    for (c2, c3) in combinations_with_replacement(squares, 2):
      # the winner got half the votes cast
      c1 = c2 + c3
      # the total number of votes cast must not be more than 1000
      if c1 > 500 or c1 not in squares: continue
      results.update((Result(*s) for s in permutations((c1, c2, c3))))
    
    # A cannot deduce the turnout (i.e. there must be multiple
    # possibilities for the total number of votes for the other two
    # candidates)
    (_, results) = filter_unique(results, (lambda v: v.A), (lambda v: v.B + v.C))
    
    # B can deduce the result
    (results, _) = filter_unique(results, (lambda v: v.B))
    
    # C can deduce the result
    (results, _) = filter_unique(results, (lambda v: v.C))
    
    # A can deduce the result
    (results, _) = filter_unique(results, (lambda v: v.A))
    
    for (A, B, C) in results:
      printf("A={A} B={B} C={C}")
    

    Solution: The Amity candidate received 225 votes. The Brotherhood candidate received 64 votes. The Comradeship candidate received 289 votes.

  2. Brian Gladman 11 April 2015 at 7:21 pm
    from itertools import combinations, permutations
    from collections import defaultdict
    
    # filter the triples in 'votes', keeping only those triples 
    # that are unique for item n in the triples
    def filter(votes, n):
      d  = defaultdict(list)
      for v in votes:
        d[v[n]].append(v)
      return sum((d[x] for x in d if len(d[x]) == 1), [])
    
    # generate possible triples for the votes cast for A, B and C
    sq = tuple(x ** 2 for x in range(1, 23))
    votes = []
    for u, v in combinations(sq, 2):
      w = v - u
      if w < u and w in sq:
        votes.extend([p for p in permutations((u, v, w), 3)]) 
    
    # A cannot determine B's and C's votes knowing their sum, so 
    # this sum cannot be unique - collect triples for A and keep
    # only those where the sum of B's and C's votes is not unique 
    d = defaultdict(list)
    for v in votes:
      d[v[0]].append(v)
    votes = sum((d[a] for a in d if len(set(b + c for a, b, c in d[a])) > 1), [])
    
    # B, C and A in turn can now determine the outcome
    for t in filter(filter(filter(votes, 1), 2), 0):
      fs = 'The votes cast for A, B and C were {}, {} and {} respectively.'
      print(fs.format(*t))
    
  3. Tessa Fullwood 12 April 2015 at 8:53 pm

    O dear, still puzzled, enquiring.

    The votes cast for A, B, C are a triple. It’s Pythagorean since c1 + c2 = c3. And c3 < 500 since votes cast < 1000.

    Valid triples are ( 9,16,25) (36,64,100) (81,144,225) (144,196,400) (25,144,169) (64,225,289)

    A cannot deduce the number of votes cast, so A belongs to more than one triple.

    If B = 25 in the triple (25,144,169) then B can deduce the votes for A and C, and deduce that the votes are not (9,16,25) since if A=9 or A=16 then A could deduce the number of votes cast.

    In the same way if B=64 in the triple (64,225,289) then B can deduce the votes for A and C.

    If the triple is (25,144,169) and C=169, then C can deduce that it is B that is 25, since if B=144 then B could not deduce the triple, as it could also be (81,144,225).

    Hence A can deduce the triple now. Where am I wrong?

    • Jim Randell 13 April 2015 at 12:23 am

      (144, 196, 400) is not a possible triple (they are all squares, but 144 + 196 ≠ 400). But (144, 256, 400) is a possible triple.

    • Hugh Casement 13 April 2015 at 1:19 pm

      Tessa,
      Being a very imperfect logician, I too puzzled, but think I got there in the end.
      √A = 15. That could be a member of the triple 9, 12, 15 or the triple 8, 15, 17. So A cannot tell the total number of votes cast, let alone what B’s and C’s shares were.
      √C = 17. The only suitable Pythagorean triple summing to <1000 is 8, 15, 17; but C still doesn't know which of the others got 8² and which 15² votes.
      √B = 8. That could be a member of the triple 6, 8, 10. But if A had either 6² or 10² votes he would know it was that triple and therefore know the total number of votes cast, which he doesn't. Therefore B knows A must have 15², which leaves 17² for C.
      Then of course C knows how many the others got.
      Imperfectly explained, but does it help at all, at all?

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: