wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Fifteen marbles
        
(Message started by: NickH on Jan 7^th, 2003, 5:36am)

Title: Fifteen marbles
Post by NickH on Jan 7^th, 2003, 5:36am

A boy has six red marbles and nine blue marbles. He arranges his fifteen marbles randomly in a row. What is the
probability that no red marble lies next to another?

Title: Re: Fifteen marbles
Post by william wu on Jan 7^th, 2003, 1:39pm

Here's my answer ... (highlight below area with mouse pointer to see)

We will compute this probability p using a counting approach. We will count the number of distinct marble arrangements which satisfy the condition that no red marbles lie next to each other, and then divide this number by the total number of distinct marble arrangements.

The total number of distinct marble arrangements is C(15,6), where C(n,k) = n! / (k! (n-k)!) = number of ways to choose k elements out of n elements.

On to the numerator. First observe that if no red marble touches each other, there must be at least one blue marble between every two would-be adjacent red marbles. Visually speaking, this much is true:

R B R B R B R B R B R

Remember that we have 9 blue marbles in total. Having fixed the positions of 5 blue marbles, only 4 blue marbles are left for us to play with, each of which can be placed either alongside one of the 4 blue marbles in the row shown above, or at the front or back ends of the row. Thus there are a total of 7 distinct locations each blue marble can be placed in. How many distinct ways are there to distribute 4 indistinguishable blue marbles amongst 7 locations? (How many ways are there to distribute 4 indistinguishable balls in 7 bins?)

A stars-and-bars counting technique can be helpful here. We will represent a blue marble by a "star" (*), and the dividing line between two adjacent locations by a "bar" (|). So you would interpret the string

* | * | | * * | | |

as saying "There are seven locations. 1st and 2nd locations both have one marble. 4th location has two marbles. Rest have zero marbles." Note that if there are 7 locations, 6 bars are needed to establish them. Thus we wish to count the number of stars-and-bar strings like the one above. Well, there are a total of 4 + 6 = 10 symbols in the string, and 4 of them must be stars. Thus the answer is C(10,4).

Conclusively, p = C(10,4) / C(15,6) ~= .042