In school $100$ kids are making necklaces from $11$ beads. Every kid gets this same set of beads: red , green, blue. Choose the sets which allow every kid to make different necklace:

a) 7-red, 2-green, 2-green

b) 7-red, 3-green, 1-blue

c) 6-red, 4-green, 1-blue

d) 8-red, 2-green, 1-blue

e) 3-red, 1-green, 7-blue

I was trying to do this with a lot of ways for example:

a) $$ \frac {11!}{7!\cdot 2!\cdot 2!} = 1980 $$ which should give the all possible ways of making different necakles, but doing this that way gives for all sets numbers higher than $100$ so all answers would be true, but in my book the good answers are only a) and c).

I don't know there is a mistake in a book or my way of doing this is wrong.

I will be very thankful for every help.

  • 1
    $\begingroup$ necakle -> necklace $\endgroup$ – Jean Marie Jan 28 '17 at 22:12
  • $\begingroup$ I am so sorry for mistakes. English is not my native language $\endgroup$ – MatNovice Jan 28 '17 at 22:20
  • 1
    $\begingroup$ The necklace is a circle - perhaps you need to divide all your answers by 11 to compensate for the fact that the answers you got assumed that there was a beginning and an end to each string of beads. $\endgroup$ – WW1 Jan 28 '17 at 22:25
  • $\begingroup$ @Serek nor mine. Don't be worried by my remark, it was only intended to have the most readable text. $\endgroup$ – Jean Marie Jan 28 '17 at 22:37

The cycle index $Z(C_{11})$ of the cyclic group acting on the eleven slots is very simple because $11$ is prime and we obtain

$$Z(C_{11}) = \frac{1}{11} (a_1^{11} + 10 a_{11}).$$

Substitution by PET (Polya Enumeration Theorem) now yields

$$\frac{1}{11} ((R+G+B)^{11} + 10 (R^{11}+G^{11}+B^{11})).$$

None of the proposed combinations are monochromatic containing eleven beads of the same color, hence only the first term contributes.

We have for

a. $$\frac{1}{11} {11\choose 7,2,2} = 180$$

b. $$\frac{1}{11} {11\choose 7,3,1} = 120$$

c. $$\frac{1}{11} {11\choose 6,4,1} = 210$$

d. $$\frac{1}{11} {11\choose 8,2,1} = 45$$

e. $$\frac{1}{11} {11\choose 3,1,7} = 120$$.

Hence all choices except d allow every kid to make a different necklace. What we see here is that all orbits except monochrome ones are the same size, containing $11$ configurations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.