# 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.

[enigma272]

### 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}")
```

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
d  = defaultdict(list)
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))
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)
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?

This site uses Akismet to reduce spam. Learn how your comment data is processed.