kpv@ulysses.UUCP (08/30/83)
Here's an interesting problem that I discovered about a year ago
after buying a toy for my son:
Let C = {1,2,3,...n} be a set of colors (read color 1, color 2 ...)
Suppose that you have Bi beads of color i for 1 <= i <= n.
The problem is to arrange the beads on a ring so that beads with
same color are equidistant on the ring.
I call such a ring a PERFECT RING.
Example:
Say we have beads: a,a,a, b,b,b, c,c, d,d, e,e
They can be arranged perfectly as in the following
circular permutation:
a d b e a c b d a e b c
Questions:
1. For what combinations of the number Bi's do perfect rings exist?
2. For such a combination, find an algorithm that will produce a ring.
3. If one ring exists, how many are there in all, ie, is there a formula
based on the Bi's for the number of perfect rings?
I have a few partial results and conjectures based on least common multiples.
But the full solution seems hard.
Kiem-Phong Vo, Bell Labs, Murray Hill, New Jersey
ulysses!kpv