# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1354: Sound idea

From New Scientist #2513, 20th August 2005

Joe’s daughter has been asking him for weeks to make a wind chime. So this week Joe cut a length of stainless steel tubing into 10 lengths from 1 cm to 10 cm in steps of 1 cm. He also cut out a disc from a sheet of stainless steel and drilled 10 evenly spaced holes round the perimeter and one in the centre.

Joe hung one tube from each hole and hung the disc up by a thread from its centre. That was a big mistake as the disc tilted right over.

So Joe rearranged the tubes until the disc balanced perfectly. In making a note of the lengths of the tubes in order round the disc the result was an 11-digit number.

What is the smallest of all the 11-digit numbers Joe could have written down?

[enigma1354]

### 5 responses to “Enigma 1354: Sound idea”

1. Jim Randell 20 January 2014 at 9:17 am

This Python program calculates the centre of mass for each arrangement of tubes, and then determines the smallest of the numbers corresponding to balanced discs. Since it’s using Python’s floats it checks the centre of mass is “close enough” to the centre of the disc. For a completely accurate (but slower) solution, you can import sin, cos, pi from sympy (instead of math), and check of the centre of mass corresponds exactly to the centre of the disc – you get the same results.

The Python program below runs in 291ms (under PyPy).

```from math import sin, cos, pi
from itertools import permutations
from enigma import Accumulator, irange, nconcat, printf

# centre of mass of particles placed around the disc
def mass(ps):
n = len(ps)
s = 2 * pi / n
x = y = M = 0
for (i, m) in enumerate(ps):
M += m
x += m * cos(i * s)
y += m * sin(i * s)
return (x / M, y / M)

# tolerance
T = 1e-12

# lets place 10 (the lexicographically lowest number in the first
# position), and consider the remaining lengths
r = Accumulator(fn=min)
for s in permutations(irange(1, 9)):
# eliminate duplicate solutions
if not(s[0] < s[-1]): continue
ps = (10,) + s
(x, y) = mass(ps)
if abs(x) < T and abs(y) < T:
n = nconcat(ps)
r.accumulate(n)
printf("[{ps} -> {n}]")

printf("min = {r.value}")
```

Solution: The smallest 11-digit number is 10145892367.

2. Brian Gladman 20 January 2014 at 2:07 pm
```
from itertools import count, permutations
from math import pi, sin, cos

# sines and cosines for positions around the circle
ci = tuple(cos(pi * i / 5.0) for i in range(10))
si = tuple(sin(pi * i / 5.0) for i in range(10))
# marker to signal that minimum has (not) been found
sentinel = 11000000000
# put the 10cm chime at angle zero and then look for
# a balance with chimes 1, 2, ... in the next position
chime, min_no = 0, sentinel
while min_no == sentinel:
chime += 1
# now permute the remaining values and check for a minimum
# value of the 11 digit number
for cc in permutations(set(range(1, 10)) - set((chime,))):
chimes = (10, chime) + cc
# check for a balance
v = sum(x * ci[j] for j, x in enumerate(chimes))
h = sum(x * si[j] for j, x in enumerate(chimes))
if v * v + h * h < 1e-10:
# if the arrangement is balanced, check if the
# number is less than any previously seen
no = int(''.join(str(x) for x in chimes))
if no < min_no:
min_no = no
print('The minimum number is', min_no)
```
• Brian Gladman 21 January 2014 at 2:45 pm

Here is a version that avoids the approximations involved in using floating point arithmetic by using complex integers (x + i.y with x and y integer) to represent the algebraic cosine and sine values.

```from itertools import permutations

# sines and cosines for positions around the circle
# (algebraic numbers are represented by complex values)
ci = ( ( 4+0j), ( 1+1j), (-1+1j), ( 1-1j), (-1-1j),
(-4+0j), (-1-1j), ( 1-1j), (-1+1j), ( 1+1j) )
si = ( ( 0+0j), ( 1-1j), ( 1+1j), ( 1+1j), ( 1-1j),
( 0+0j), (-1+1j), (-1-1j), (-1-1j), (-1+1j) )
# put the 10cm chime at angle zero and then look for
# a balance with chimes 1, 2, ... in the next position
chime, nbrs = 0, []
while not nbrs:
chime += 1
# now permute the remaining values and check for a minimum
# value of the 11 digit number
for cc in permutations(set(range(1, 10)) - set((chime,))):
chimes = (10, chime) + cc
# check for a balance
if not (sum(x * ci[j] for j, x in enumerate(chimes)) or
sum(x * si[j] for j, x in enumerate(chimes))):
# if the arrangement is balanced, check if the
# number is less than any previously seen
nbrs += [int(''.join(str(x) for x in chimes))]
print('The minimum number is', min(nbrs))
```
3. arthurvause 21 January 2014 at 10:48 am

Here is another variation. The reasoning behind the code is in a Blog post

```from itertools import permutations as perm

a=10
onetoten=frozenset(range(1,11))

for b,c,d,e in perm(range(1,10),4):
f=55-a-2*(b+c+d+e)
g=55-b-2*(c+d+e+f)
h=55-c-2*(d+e+f+g)
i=55-d-2*(e+f+g+h)
j=55-e-2*(f+g+h+i)

s=(a,b,c,d,e,f,g,h,i,j)
if set(s)==onetoten:

# sanity check
if all( sum(s[i%10] for i in xrange(m,m+4))
==sum(s[i%10] for i in xrange(m+5,m+9))
for m in xrange(10)):
print "solution", a,b,c,d,e,f,g,h,i,j
break
```
4. Jim Randell 23 January 2014 at 9:46 am

This is a recursive Python solution that uses the analysis that opposite pairs of adjacent weights sum to the same value (i.e if the weights are numbered from w0 to w9 around the circle, then w0 + w1 = w5 + w6, w1 + w2 = w6 + w7, w2 + w3 = w7 + w8, w3 + w4 = w8 + w9, w4 + w5 = w9 + w0).

It runs in 35ms – much faster than computing the centre of mass of all combinations.

```from enigma import Accumulator, nconcat, irange, printf

# update a list with a sequence of (index, value) pairs
def update(ws, *args):
r = list(ws)
for (i, w) in args:
r[i] = w
return r

# ws - weights allocated so far
# rs - remaining weights
# i - next index to allocate
# r - accumulator for solution
def solve(ws, rs, i, r):
# are we done?
if not rs:
# eliminate mirror image solutions
if ws[1] < ws[-1]:
n = nconcat(ws)
r.accumulate(n)
printf("{ws} -> {n}")
else:
# choose a weight to place at the next index
for w0 in rs:
# and determine the opposite weight
w1 = w0 + ws[i - 1] - ws[i + 4]
if w1 != w0 and w1 in rs:
solve(update(ws, (i, w0), (i + 5, w1)), rs.difference((w0, w1)), i + 1, r)

# place 10 at position 0, and all other possible weights opposite (position 5)
ws = [10] + [None] * 9
rs = set(irange(1, 9))
r = Accumulator(fn=min)
for w in rs:
solve(update(ws, (5, w)), rs.difference([w]), 1, r)

# output the minimal solution
printf("min = {r.value}")
```

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