# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1290: Marbled patterns

From New Scientist #2448, 22nd May 2004 [link]

I laid out a row of identical saucers and gave my nephew some marbles, all the same. I then set him the following problem:

“If I ask you to place all the marbles in the saucers, with at least one marble in each, in how many ways can this be done?”

After some thought he came to the correct conclusion that there were between a thousand and ten thousand such arrangements, and then he gave up. So I then asked him the following simpler question:

“How many of these arrangements will be symmetrical, in the sense that if I reversed the order of the saucers the pattern remains the same?”

This time he gave the correct answer of 20.

What was the correct answer to the first question?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1290]

### 5 responses to “Enigma 1290: Marbled patterns”

1. Jim Randell 29 September 2014 at 1:51 pm

If there is one saucer then there is only one possible arrangement, and it is symmetrical.

If there are two saucers then there can be at most one symmetrical arrangement, when there are an even number of marbles, with half in each saucer.

So, this program, which looks for numbers of marbles and saucers with 20 symmetrical arrangements, starts looking from 3 saucers.

When considering s saucers it looks for m marbles (with m > s) such that there are between 1,000 and 10,000 arrangements (the number of arrangements is strictly increasing with the number of marbles).

It constructively determines the number of arrangements by counting and runs in 221ms

```from itertools import count
from collections import defaultdict
from enigma import irange, cached, printf

# how many arrangements of m marbles in s saucers (m >= s)
@cached
def A(m, s):
# if s = 1 or s = m, there is only one arrangement
if s == 1 or s == m: return 1
# choose a number of marbles for the first saucer
# and arrange the remaining marbles
return sum(A(m - m1, s - 1) for m1 in irange(1, m - s + 1))

# and how many symmetrical arrangements
def S(m, s):
# if there's only s == 1 or s == m there's only 1 arrangement
if s == 1 or s == m: return 1
(m2, rm) = divmod(m, 2)
(s2, rs) = divmod(s, 2)
# if there's an even number of saucers
if rs == 0:
# we need an even number of marbles
if rm == 1: return 0
# arrange half the marbles in half the saucers
return A(m2, s2)
else:
# choose how many marbles to place in the central saucer
# and arrange half the remaining marbles in half the saucers
return sum(A((m - m1) // 2, s2) for m1 in irange(2 - rm, m - s + 1, step=2))

# accumulate results by A(m, s)
r = defaultdict(list)

# consider increasing numbers of saucers
for s in count(3):
# and possible numbers of marbles (m > s)
for m in count(s + 1):
# there should be between 1000 and 10000 arrangements
a1 = A(m, s)
if a1 < 1000: continue
if a1 > 10000: break
# and 20 symmetrical arrangements
a2 = S(m, s)
if a2 != 20: continue
printf("[{s} saucers, {m} marbles, A={a1}, S={a2}]")
r[a1].append((m, s))
# we are done when there are no arrangements below 10000
if m == s + 1: break

# display the results
for k in sorted(r.keys()):
printf("A={k} [{s}]", s=' '.join("m=" + str(m) + ',s=' + str(s) for (m, s) in r[k]))
```

Solution: The answer to the first question is 1716. (i.e. there are 1716 different ways of arranging the marbles in the saucers).

This can be achieved with 14 marbles and either 7 or 8 saucers.

• Jim Randell 29 September 2014 at 1:51 pm

Here’s an analytic solution:

It turns out that for 3 saucers the number of arrangements follows the triangular numbers:

A(n + 3, 3) = T(n + 1) = (n + 2)(n + 1)/2 = C(n + 2, 2)

For 4 saucers it follows the tetrahedral numbers:

A(n + 4, 4) = C(n + 3, 3)

And in general it follows the n-dimensional triangular numbers:

A(m, s) = C(m – 1, s – 1)

For the symmetrical case we get:

S(m, s) = C(m/2 – 1, s/2 – 1) if s is even and m is even
S(m, s) = C(m/2 – 1, (s – 1)/2) if s is odd and m is even
S(m, s) = C((m – 1)/2, (s – 1)/2) if s is odd and m is odd
S(m, s) = 0 if s is even and m is odd

So if S(m, s) = 20 we need to find p and q where C(p, q) = 20.

Possible values for (p, q) are (6, 3), (20, 1), (20, 19).

Case 1: (p, q) = (6, 3) corresponds to (m, s) = (14, 8), (14, 7), (13, 7).

And A(14, 8) = 1716, A(14, 7) = 1716, A(13, 7) = 924.

This gives rise to two solutions: (m, s) = (14, 8), (14, 7) in each case A(m, s) = 1716.

Case 2: (p, q) = (20, 1) corresponds to (m, s) = (42, 4), (42, 3), (41, 3).

And A(42, 4) = 10660, A(42, 3) = 820, A(41, 3) = 780.

This gives rise to no further solutions.

Case 3: (p, q) = (20, 19) corresponds to (m, s) = (42, 40), (42, 39), (41, 39).

And A(42, 40) = 820, A(42, 39) = 10660, A(41, 39) = 780.

This also gives rise to no further solutions.

2. Julian Gray 17 December 2014 at 3:23 pm

Did anyone else find that 19 marbles and 5 saucers produces 20 palindromic arrangements? I did it the hard way (I’m a mere engineer, or rather I was, and I cannot match Jim’s analytical and programming skills).

3. Jim Randell 17 December 2014 at 9:11 pm

If you want to see the possible arrangements here is my program adjusted to print them out:

```from enigma import irange, printf

# generate arrangements of m marbles in s saucers
def A(m, s):
if s == 1:
# 1 saucer, put all the marbles in it
yield [m]
elif s == m:
# same number of saucers and marbles, 1 in each
yield [1] * s
else:
# choose a number of marbles for the first saucer
for m1 in irange(1, m - s + 1):
# and arrange the remaining marbles
for r in A(m - m1, s - 1):
yield [m1] + r

# generate symmetrical arrangements
def S(m, s):
if s == 1:
# 1 saucer, put all the marbles in it
yield [m]
elif s == m:
# same number of saucers and marbles, 1 in each
yield [1] * s
else:
(m2, rm) = divmod(m, 2)
(s2, rs) = divmod(s, 2)
# if there's an even number of saucers
if rs == 0:
# we need an even number of marbles
if rm == 0:
# arrange half the marbles in half the saucers
for r in A(m2, s2):
# and mirror it
yield r + r[::-1]
else:
# there's an odd number of saucers
# choose how many marbles to place in the central saucer
for m1 in irange(2 - rm, m - s + 1, step=2):
# and arrange half the remaining marbles in half the saucers
for r in A((m - m1) // 2, s2):
# and mirror it
yield r + [m1] + r[::-1]

import sys
m = (14 if len(sys.argv) < 2 else int(sys.argv[1]))
s = ( 7 if len(sys.argv) < 3 else int(sys.argv[2]))
fn = ('S' if len(sys.argv) < 4 else sys.argv[3])

assert not(m < s) and fn in ('A', 'S')
printf("{fn}(m={m}, s={s})")
fn = (A if fn == 'A' else S)

n = 0
for r in fn(m, s):
n += 1
printf("{n}: {r}")
```

For example, for the 36 symmetrical (S) arrangements of 19 marbles in 5 saucers:

```% python enigma1290z.py 19 5 S
S(m=19, s=5)
1: [1, 8, 1, 8, 1]
2: [2, 7, 1, 7, 2]
3: [3, 6, 1, 6, 3]
4: [4, 5, 1, 5, 4]
5: [5, 4, 1, 4, 5]
6: [6, 3, 1, 3, 6]
7: [7, 2, 1, 2, 7]
8: [8, 1, 1, 1, 8]
9: [1, 7, 3, 7, 1]
10: [2, 6, 3, 6, 2]
11: [3, 5, 3, 5, 3]
12: [4, 4, 3, 4, 4]
13: [5, 3, 3, 3, 5]
14: [6, 2, 3, 2, 6]
15: [7, 1, 3, 1, 7]
16: [1, 6, 5, 6, 1]
17: [2, 5, 5, 5, 2]
18: [3, 4, 5, 4, 3]
19: [4, 3, 5, 3, 4]
20: [5, 2, 5, 2, 5]
21: [6, 1, 5, 1, 6]
22: [1, 5, 7, 5, 1]
23: [2, 4, 7, 4, 2]
24: [3, 3, 7, 3, 3]
25: [4, 2, 7, 2, 4]
26: [5, 1, 7, 1, 5]
27: [1, 4, 9, 4, 1]
28: [2, 3, 9, 3, 2]
29: [3, 2, 9, 2, 3]
30: [4, 1, 9, 1, 4]
31: [1, 3, 11, 3, 1]
32: [2, 2, 11, 2, 2]
33: [3, 1, 11, 1, 3]
34: [1, 2, 13, 2, 1]
35: [2, 1, 13, 1, 2]
36: [1, 1, 15, 1, 1]
```

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