A solution to the problem on the previous page
is pictured on the left. We need 21 beads, 16 black and 5 yellow.
Instead of drawing beads, we may also represent the necklaces by sequences of numbers as follows: Choose any yellow bead (say, the rightmost yellow one in the picture) and call this bead `number zero'. Now count beads clockwise and assign subsequent numbers 1,2,... to subsequent beads. Write down all numbers that correspond to a yellow bead and stop when you reach the original bead again.
For the necklace in the picture, this yields the following sequence :
0 5 6 9 19 21
Applying the same procedure to the 13-bead necklace
on the previous page
results in the following numbers:
0 3 5 12 13
Obviously every sequence starts with 0. Also note that the last number in the sequence always indicates the total number of beads.
The number of yellow beads is equal to the number of elements in the sequence, minus 1. For that reason, we usually write the last number in between parentheses, or omit it altogether:
0 5 6 9 19 (21)
Clearly not all possible sequences correspond to `weird' necklaces in
this way. For a start, all numbers must be in order and no two numbers
must be equal. But this is still not sufficient.
To check this, we set up a table of the following form:
0 5 6 9 19 (21)
-------------------
0| 0 5 6 9 19
5| -5 0 1 4 14
6| -6 -1 0 3 13
9| -9 -4 -3 0 10
19|-19 -14 -13 -10 0
Each element in this table is the difference between the top element
in the same column and the front element in the same row. For
example, the element 10 on the 4th row and 5th column is the
difference between the 5th element of the sequence (19) and the 4th
(9). The diagonal elements are all zero. The elements to the left of
the diagonal are all negative and correspond to their positive `mirror'images
to the right of the diagonal.
Now leave out the table headings and add 21
(i.e., the total number of beads in the necklace) to
every negative element in this table. You obtain the following table:
0 5 6 9 19 (21) 16 0 1 4 14 15 20 0 3 13 12 17 18 0 10 2 7 8 11 0The resulting table is called the difference table for the given 21-bead necklace.
Note that, apart from the 5 zeroes on the diagonal, all entries in this table are different. This is the mathematical way of stating that the necklace is `weird'. Before we give an exact mathematical formulation of this property, you should give some thought to why this is true. It may help to note that adding 21 to the negative numbers corresponds to counting the beads in the opposite sense.
Here is the difference table for the 13-bead example:
0 3 5 12 (13) 10 0 2 9 8 11 0 7 1 4 6 0
Cyclic difference sets.
96/12/30 - Kris Coolsaet