# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1700: Polymagic

From New Scientist #2867, 2nd June 2012 [link]

From a box of counters numbered 1 to 12, Joe asked Penny to select a set of six and place them on the corners of a regular hexagon and then place the remaining six counters on the mid-points of each side, so that the number on each of these counters was the sum of the numbers on the counters on the two adjacent corners. Joe then produced 16 counters and asked Penny to repeat the challenge, but this time selecting a set of eight and placing them, and the remaining eight, similarly on an octagon.

In the first case, Penny found her choice of the set of six counters was rather limited. How many choices did she have?

And how many choices did she have in the case of the octagon?

[enigma1700]

### 12 responses to “Enigma 1700: Polymagic”

1. Jim Randell 30 May 2012 at 6:47 pm

The following Python program runs in 44ms.

```from itertools import combinations, permutations
from enigma import irange, printf

def solve(n):
# what are the values on the counters?
ns = set(irange(1, n * 2))
# the number of each vertex will be part of the sum on two edges,
# hence if t is the sum of the vertices, t + 2t = sum(ns)
(t, r) = divmod(sum(ns), 3)
# so there is no solution unless sum(ns) is divisible by 3
if r > 0: return 0

# to eliminate duplicate solutions we will assume that the first
# vertex has the lowest number, and the second vertex is numbered
# lower than the final vertex

ss = set()
# find possible combinations for the vertices, except the final one
for cs in combinations(ns, n - 1):
# the first vertex
a = min(cs)
# the final vertex
z = t - sum(cs)
if not(a < z): continue
if not(z in ns.difference(cs)): continue
# remove the first vertex
cs = set(cs).difference((a,))
# consider permutations of the vertices (except the first and last)
for ps in permutations(cs):
# check the second vertex is lower than the final vertex
if not(ps[0] < z): continue
# consider all the vertices (as a circular list)
vs = [a] + list(ps) + [z, a]
# and determine the values on the edges
es = list(vs[i] + vs[i+1] for i in range(n))
# check the edges and vertices correspond to the counters
if set(es).union(vs[:-1]) != ns: continue
# what are the vertices?
return len(ss)

for n in (6, 8):
printf("n={n}: {s} choices", s=solve(n))
```

Solution: For the hexagon Penny could choose from 4 different sets of counters. For the octagon there are no sets of counters that will give a solution.

• Jim Randell 31 May 2012 at 7:36 am

Here’s a slightly modified version that additionally uses the fact that the two lowest numbers must be vertices, and the two highest numbers must be edges. It doesn’t run noticeably faster, but running it under [[ `cProfile` ]] reveals that the number of function calls goes down from ~5500 to ~2900.

It also uses a [[ `Counter` ]] object to track both the number of solutions and the number of different sets of counters used on the vertices in those solutions.

```from itertools import combinations, permutations
from collections import Counter
from enigma import irange, printf

def solve(n):
# what are the values on the counters?
ns = list(irange(1, n * 2))
# the number of each vertex will be part of the sum on two edges,
# hence if t is the sum of the vertices, t + 2t = sum(ns)
t, r = divmod(sum(ns), 3)
# so there is no solution unless sum(ns) is divisible by 3
if r > 0: return (0, 0)

# the lowest two numbers must be placed on vertices, as they cannot
# form a sum, and likewise the highest two numbers must be placed on
# edges, as they must form a sum

# to eliminate duplicate solutions we will assume that the first
# vertex has the lowest number, and the second vertex is numbered
# lower than the final vertex

# so the first vertex is 1, and 2 is also a vertex (not the final one)

c = Counter()
# find possible combinations for the remaining vertices
for cs in combinations(ns[2:-2], n - 3):
# the final vertex
z = t - sum(cs) - sum(ns[0:2])
if not(z in set(ns[2:-2]).difference(cs)): continue
# consider permutations of the vertices (except the first and last)
for ps in permutations(set(cs).union(ns[1:2])):
# check the second vertex is lower than the final vertex
if not(ps[0] < z): continue
# consider all the vertices (as a circular list)
vs = [ns[0]] + list(ps) + [z, ns[0]]
# and determine the values on the edges
es = list(vs[i] + vs[i + 1] for i in range(n))
# check the edges and vertices correspond to the counters
if set(es).union(vs[:-1]) != set(ns): continue
# what are the vertices?
printf("[n={n}] vertices={vs} edges={es}", vs=vs[:-1])
c[tuple(sorted(vs[:-1]))] += 1
return sum(c.values()), len(c)

for n in (6, 8):
s, c = solve(n)
printf("n={n}: {s} solutions, {c} choices")
```
2. Brian Gladman 30 May 2012 at 10:53 pm

Hi Jim,
Here is my solution:

```from itertools import permutations

def solve(n):
# the sum of the edge counters is twice the sum of
# the vertex counters - so vertex counter sum is
# 1/3 of the sum of the counter values (1 .. 2n)
d, r = divmod(n * (2 * n + 1), 3)
if r:
return None
cnt = 0
s = set(range(1, 2 * n + 1))
# counter 1 must be a vertex counter
# the maximum vertex counter is 2 * n - 2
# permute n - 2 values
for p in permutations(range(2, 2 * n - 1), n - 2):
# now add the first and last vertexes
q = (1,) + p + (d - 1 - sum(p),)
# avoid counting solutions that are the same
# clockwise and counterclockwise
if q[1] < q[-1]:
# compute the edge values
t = tuple(q[i] + q[(i + 1) % n] for i in range(n))
# and check we have a full set of counter values
if set(t) | set(q) == s:
cnt += 1
return cnt

print('Solutions for a hexagon:', solve(6))
print('Solutions for a octagon:', solve(8))
```

I get a different answer compared with your code – I am doubtful that your line of code:
should sort the vertexes in compiling the set of solutions as I think the vertex order matters.
Brian

• Jim Randell 30 May 2012 at 11:07 pm

I agree that in the hexagonal case there are 6 different solutions, but in two cases the solution uses the same collection of counters as two of the other solutions. Which in a strict reading of the problem means there are only 4 possible sets of counters that can be chosen to solve the first part of the problem.

3. Brian Gladman 31 May 2012 at 6:33 am

Good point Jim, I didn’t read it that way but it does look as if that is what is intended.

4. Brian Gladman 31 May 2012 at 10:19 am

Here is a corrected version of my code:

```from itertools import permutations

def solve(n):
# the edge counter sum is twice the vertex counter sum
# hence the vertex counter sum is 1/3 the counter sum
vertex_sum, r = divmod(n * (n + n + 1), 3)
if r:
return None
ctrs, sol_set = set(range(1, 2 * n + 1)), set()
# vertex counters include 1 and have maximum values of
# 2n - 2 so assume these are '1, (n - 2) values, last'
# and permute the middle n - 2 values
for p in permutations(range(2, 2 * n - 1), n - 2):
# now add the first and last vertex counter values
q = (1,) + p + (vertex_sum - 1 - sum(p),)
# avoid the same solutions clockwise/counterclockwise
if q[1] < q[-1]:
# compute the edge values
t = tuple(q[i] + q[(i + 1) % n] for i in range(n))
# and check we have the full set of counter values
if set(t) | set(q) == ctrs:
sol_set |= set((tuple(sorted(q)),))
return len(sol_set)

print('Solutions for a hexagon:', solve(6))
print('Solutions for a octagon:', solve(8))
```
5. arthurvause 31 May 2012 at 2:58 pm

The sum of the counters on mid-points = 2 x sum of the counters on the corners, so the sum of counters on corners is 1/3 of the sum of all counters.

For 12 counters, the sum of all counters is 13×6 (a multiple of 3).

For 16 counters the sum of all counters is 17×8, not a multiple of 3, so we don’t need to write any code for this option.

Also, (as Jim observed), 1 and 2 must be on corners, 11 and 12 must be on mid-points.

So, a bit of code:

```import itertools

count=0
print "Solutions (including reflections):"
edges = range(3,11)
for x in itertools.combinations(edges, 4):
if sum(x) + 3 == 26:
x+=(2,)
for y in itertools.permutations(x):
s = set([y[0]+1,y[0]+y[1],y[1]+y[2],y[2]+y[3],y[3]+y[4],y[4]+1])
s|=set(y)
if s==set(range(2,13)):
y+=(1,)
count+=1
print y
print "Count, ignoring reflections, = ", count/2
```

I am taking the view that permutations that are not reflections or rotations of each other count as different choices, e.g. 2, 5, 6, 4, 8, 1 is different to 2, 8, 4, 5, 6, 1, hence the answer of 6 rather than 4.

6. Brian Gladman 31 May 2012 at 3:43 pm

Initially I also gave 6 rather than 4 as the answer but I think Jim is right that the answer to the actual question posed in this enigma is 4, the number of different sets of vertex counters, irrespective of their order.

• arthurvause 31 May 2012 at 4:04 pm

I think you are right, as otherwise the count would need to include rotations and reflections as well as other permutations of vertex counters.

7. Jim Randell 1 June 2012 at 8:34 am

As a variation here is a recursive solution. It’s quicker than using [[ `itertools` ]] for larger values of n. For example it finds 12932 solutions (556 different sets) when n=12 in under 20s. (My other algorithm took over an hour before I stopped it).

```from collections import Counter
from enigma import irange, printf

# n = target length
# vs = vertices
# es = edges
# ns = numbers
# c = counter for solutions
def solve(n, vs, es, ns, c):
# are we done?
if len(vs) == n:
# for uniqueness
if not(vs[1] < vs[-1]): return False
# check the final edge
e = vs[-1] + vs[0]
if e not in ns: return False
printf("[n={n}] vertices={vs} edges={es}", es=es + [e])
c[tuple(sorted(vs))] += 1
return True

# try the next vertex
for v in ns:
e = v + vs[-1]
if e not in ns: continue
solve(n, vs + [v], es + [e], ns.difference((v, e)), c)

import sys
n = 6 if len(sys.argv) < 2 else eval(sys.argv[1])

c = Counter()
solve(n, [1], [], set(irange(2, n * 2)), c)
printf("n={n}: {s} solutions, {l} choices", s=sum(c.values()), l=len(c))
```
• Jim Randell 5 June 2012 at 11:49 am

Here are the results for values of n from 2 to 18:

```n = number of vertices of shape
s = number of solutions
d = number of different vertex sets

n             s         d

2             0         0
3             1         1
4             1         1
5             0         0
6             6         4
7            17         8
8             0         0
9           148        42
10           578        92
11             0         0
12        12_932       556
13        70_092     1_274
14             0         0
15     2_505_240     7_628
16    16_826_503    18_162
17             0         0
18   915_013_780   111_051
```
8. Brian Gladman 2 June 2012 at 9:19 am

Good work Jim!.

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