9
$\begingroup$

I'm trying to resolve this simple problem:

We have $10$ beads, of which $8$ are white and $2$ are red and otherwise indistinguishable. In how many ways can we place the beads so that $2$ red beads are always separated?

I think that this is a simple permutation with repetition so i've done this:

$$ P = \frac{10!}{8!2!} - 9 $$

$9$ are the permutation of the $2$ red beads when they are close to each other. In this way the result is $36$. Anyway the answer should be $$ 10! - 8!2! $$ I don't understand what is wrong , so please let me know. Thank you.

$\endgroup$
2
  • 2
    $\begingroup$ To put it simple, the 1st answer is correct if the beads are indistinguishable, and the 2nd answer is correct if the beads are distinguishable. $\endgroup$ Jan 4 '17 at 11:23
  • $\begingroup$ The underlying problem is that "indistinguishable" may or may not be relevant to counting the number of permutations. The literal wording of the question makes "indistinguishable" irrelevant - how many ways can you place the beads. The use of the term "indistinguishable" implies a different problem - how many unique patterns can be made with the beads. $\endgroup$
    – Glen O
    Jan 4 '17 at 13:36
8
$\begingroup$

The biggest problem here is that the question is not well defined, but sloppily written so as to rely on a great many implicit assumptions. As such the best we can do is guess as to which interpretation the authors intended, and attempt to find an interpretation such that the answer they provide matches the answer we can compute.

We have $10$ beads, of which $8$ are white and $2$ are red and otherwise indistinguishable. In how many ways can we place the beads so that $2$ red beads are always separated?

The first imprecision: Are the $8$ white beads indistinguishable from each other? Or is it only the $2$ red beads which are indistinguishable from each other? Considering the word "otherwise" it must be that the only distinguishing factor between any beads is color; however this is not even a properly phrased English sentence. Instead we might say:

We have $10$ beads, of which $8$ are white and $2$ are red. Beads of the same color are indistinguishable.

Next: Note that there are NO limitations placed on how the beads are to be arranged. They could be placed in a circle, or in a pair of straight lines, or we could ship one red bead to New York and the other to Chicago (that should "separate" them sufficiently) and place the remaining $8$ beads into miscellaneous geometric patterns. So the true answer to this riddle as stated is, "There is no limit."

I surmise that we are supposed to assume that the beads are to be placed consecutively in a single straight line, and that at least one white bead must be in between the two red beads for an arrangement to be valid. However, it is extremely sloppy for a math problem to be stated in such imprecise terms.


However, if we take the preceding paragraph as the intended, valid interpretation, then the computation is very simple:

Place the first red bead in any one of the ten positions, and the other red bead in any one of the remaining nine positions. This is $10 \times 9 = 90$ possibilities to start with. Divide by $2$ to remove double counting, which gives $45$. Subtract the $9$ illegal possibilities that include adjacent red beads, for a final answer of $36$.

You are right and the book is wrong (in more ways than one.)


I've considered it, and I can't think of any possible interpretation of the puzzle which would validate the stated "correct" answer from the book. Not even if we change the puzzle drastically and entirely can I come up with that figure.

(I hope you're not trying to learn any actual new ideas from this book. It looks likely that you'll be taught them sloppily and incorrectly.)

$\endgroup$
1
  • 1
    $\begingroup$ I think the book answer is a typo. If the book considers different beads of the same color in the same position to be different (but indistinguishable) arrangements [in which case they should NOT have stated they were indistinguishable] then for each of the OP's (correct) 10!/8!2! - 9 ways that the two white beads can't be together, there are 8!2! ways to place the 8 different (but indistinguishable) red and 2 different white beads. So the book would want $8!2!(10!/8!2! - 9) = 10! - 9*8!*2! = 10! - 9!2!$. Maybe that is what the book meant. But, I'm with you. The book screwed up. $\endgroup$
    – fleablood
    Jan 4 '17 at 21:00
4
$\begingroup$

Your logic and your answer are correct. There may be some typo in the given answer.

Since the beads are indistinguishable, the possible ways to place them are $$\dbinom{10}{2}=\frac{10!}{8!2!}$$ since you only need to specify where to put the $2$ read beads. Now, indeed, if you "merge" the $2$ read beads in $1$ you have a total of $9$ beads, which you can place in $$\dbinom{9}{1}=9$$ ways, which implies that the correct answer is $$\frac{10!}{8!2!}-9=36$$ as you have it.

$\endgroup$
4
$\begingroup$

If the beads are indistinguishable, then the number of arrangements is:

$$\frac{(8+2)!}{8!\times2!}-\frac{(8+1)!}{8!\times1!}=36$$


If the beads are distinguishable, then the number of arrangements is:

$$(8+2)!-9!\times2!=31933440$$

$\endgroup$
1
  • $\begingroup$ @CarstenS: Yes, it should!!! Thank you for the correction :) $\endgroup$ Jan 4 '17 at 20:33
1
$\begingroup$

Another way you can think of it is;

Suppose you arrange the 8 white beads first. Then there is only 1 way that you can do so. Observe that there are 9 slots (denoted by the _) that I can insert my 2 red beads in such that my red beads are not adjacent to each other.

_W_W_W_W_W_W_W_W_

All I have to do is choose 2 positions out of the 9 to fit my red beads in, then I would have obtained that answer 36 as well. ( 9C2 = 36 )

Hope it helps!

$\endgroup$

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.