### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,820 hits

Advertisements

Programming Enigma Puzzles

29 September 2014

Posted by on **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]

Advertisements

%d bloggers like this:

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

ssaucers it looks formmarbles (withm>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

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.

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.

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

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

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

Oh yes! You are so right, putting the engineer to shame! Thanks. Julian