A circular necklace contains
n beads. Each bead is black or white. How many
different necklaces can be made with
n beads?
There is no clasp to identify a specific point on the chain, and a flipped over necklace is still the same necklace.
_____________________________
To get you started:
With 1 bead, the necklace can be either 1 black or 1 white bead.
With 2 beads, the necklace can be either 2 black, 2 white, or 1 black1 white
With 3 beads, the necklace can be either 3 black, 3 white, 2 black1 white, 2 white1 black, etc...
# Beads Number of Necklaces
1 2
2 3
3 4
4 6
5 8
6 13
(In reply to
re(6): There is an error is this puzzle by Thalamus)
I did read the problem carefully, even though Penny evidently did not (at least in effect, anyway). But ignoring the problem's statement that flipped, as well as rotated, necklaces are equivalent, there are 14 6bead necklaces with beads of 2 colors, and Penny's program found exactly that number. What is really interesting is that of these 14 necklaces, 12 are flipequivalent to themselves, whereas 2 of them are flipequivalent to one another. Thus the flipping made only a difference of 1 in the result, and Penny's program was a correct solution of the "unflipped" problem, not a bugridden attempt at solving the problem as stated.

Posted by Richard
on 20040821 13:16:55 