Try this!

Denis · **Posted:** Sat, 14 Mar 2009 18:47:10 UTC

12 candies: 2 black, 2 blue, 2 purple, 2 red, 2 white, 2 yellow.

6 jars: jar A, jar B, jar C, jar D, jar E, jar F.

The 12 candies are dropped at random in the jars, 2 in each jar.

What's the probability that AT LEAST one jar contains 2 candies of same color?

Soroban · **Posted:** Sun, 15 Mar 2009 02:38:16 UTC

Hello, Denis!

I think I've got it, but normally I miscount somewhere . . . *blush*

Quote:

12 candies: 2 black, 2 blue, 2 purple, 2 red, 2 white, 2 yellow.
6 jars: jar A, jar B, jar C, jar D, jar E, jar F.
The 12 candies are dropped at random in the jars, 2 in each jar.
What's the probability that AT LEAST one jar contains 2 candies of same color?

There are: . $${12\choose2,2,2,2,2,2} \:=\:7,484,400$ ways to place the candles.

How many of these have no matching pairs of colors?

Place one of each color in each of the jars.
. . There are:

ways.

The other six must be placed so there are no matching pairs.
This is a derangement of the six candles. . There are: d(6) = 265

ways.

Then there are: . $6! \times 265 \:=\:190,800$ ways with no matching pairs.

Hence, there are: . $7,484,400 - 190,800 \:=\:7,293,600$ ways with some matching pairs.

Therefore: . $$P(\text{some matches}) \;=\;\frac{7,293,600}{7,484,400} \;=\;\frac{2026}{2079} \;\approx\; 97.45\%$

Denis · **Posted:** Sun, 15 Mar 2009 03:26:24 UTC

Nope; way off; probability is below 1/2.

Try a shorter one: 2 red and 2 blue with 2 jars: probability is 1/3, right?

Btw, they're CANDIES, not CANDLES :wink:

Opalg · **Posted:** Tue, 17 Mar 2009 09:57:37 UTC

Is there a neat way to approach this problem? The only method I could find was a laborious listing of cases that can occur. Following Denis's suggestion of building up to the case of six colours and six jars by starting with two of each and working upwards, I got the answer $\frac{871}{2079}\approx0.4189514$ . But like Soroban I'm not good at counting, so I'm not that confident of the accuracy of that answer. I'd be a lot happier if I could find a conceptually cleaner way to get the result.

Denis · **Posted:** Tue, 17 Mar 2009 20:02:14 UTC

That's what I got too, Opalg, but by writing a program.

Labelling the 12 candies 1 to 12 (1-2 = black .... 11-12 = yellow),
say a random result is (Jar A to F order):
7-3, 11-5, 6-1, 2-12, 9-8, 4-10
That's really the same as:
1-6, 2-12, 3-7, 4-10, 5-11, 8-9 (keep left < right)

Then check each "jar" for a difference of 1, highest being even.

Assigning variables A to L for 1 to 12, the looping goes:

A = 1
Loop B from A+1 to 12
Loop C from A+1 to 7
Loop D from C+1 to 12
Loop E from C+1 to 8
Loop F from E+1 to 12
Loop G from E+1 to 9
Loop H from G+1 to 12
Loop I from G+1 to 10
Loop J from I+1 to 12
Loop K from I+1 to 11
Loop L from K+1 to 12
Check each jar for at least one "yes":
Is B-A = 1 and B even?
...
Is L-K = 1 and L even?

Results in 4355 "yes" out of 10395 combos, hence 871/2079

Haven't been able to come up with a "neat way"...the way Soroban does!
Maybe he'll be back with one: to make up for his terrible goof in his post :wink:

Ryan's Dad · **Joined:** Mon, 21 Mar 2005 02:57:16 UTC **Posts:** 140

I couldn't find a neat general solution for n candies and n/2 jars. It's way beyond my ability. I vaguely remember once looking for but not finding a solution to the menage problem excluding the typical restriction that the seating must alternate man/woman. That seems to be a very similar problem.

I'll show my work. Not because it's any good. I'm just hoping that it might give some ideas to many of you here who are smarter and better educated than me. I doubt if this leads anywhere - so I apologize in advance if this is way off and a complete waste of everyone's time.

First I create a sequence for the color of candies drawn $\{x_1, x_2, x_3, ..., x_n\}$ , and assume they are put in the jars in order: ( x_1

and

in Jar 1,

and

in Jar 2, ...)

I list the six possible arrangements of four candies in a matrix:

$\left[\begin{array}{c c c c c c} A & A & A & B & B & B\\ A & B & B & A & A & B\\ B & A & B & A & B & A\\ B & B & A & B & A & A\\ \end{array}\right]$

I then have a matrix which describes the match status of each element in the matrix (i.e., whether or not the element matches its partner in the jar).

For odd values of

: $\begin{cases}x_{i}=x_{i+1}: \quad 1\\ x_{i} \neq x_{i+1}: -1 \end{cases}$

For even values of

: $\begin{cases}x_{i}=x_{i-1}: \quad 1\\ x_{i} \neq x_{i-1}: -1 \end{cases}$

So my "match-status" matrix for n=4 corresponding to the above outcomes is:

$M: \left[\begin{array}{c c c c c c} 1 & -1 & -1 & -1 & -1 & 1\\ 1 & -1 & -1 & -1 & -1 & 1\\ 1 & -1 & -1 & -1 & -1 & 1\\ 1 & -1 & -1 & -1 & -1 & 1\\ \end{array}\right]$

There needs to be a second status matrix which shows the potential new partner for each element if that particular element is shifted to the right by one space (assuming one candy is placed to the left and one is placed to the right). Candies can be displaced by 0, 1 or 2 spaces. If they are displaced by 0 or 2 spaces they are paired with the same candy as before. If they are displaced by 1 space, they have a new partner. For odd numbered candies, this new partner will be to the left; for even numbered candies it will be to the right.

For the above matrix, this "alternate status" matrix is as follows:

$N: \left[\begin{array}{c c c c c c} -1 & -1 & -1 & -1 & -1 & -1\\ -1 & -1 & 1 & 1 & -1 & -1\\ -1 & -1 & 1 & 1 & -1 & -1\\ -1 & -1 & -1 & -1 & -1 & -1\\ \end{array}\right]$

Now I want to get from a matrix for (n=4)

to a matrix for (n=6)

, but there are $\binom{10}{2}=90$ possible transformations. Leaving spaces for the possible locations of the next two candies we have 3n+2

spaces:
$\displaystyle\\ \displaystyle\{\_, \_, x_1, \_,\_ x_2, \_,\_, x_3, \_,\_, x_4, \_,\_, \}\\$

Let L(x_i)

represent the position of x_i

occupies in the expanded string, so L(x_i)=3i

and the empty spaces are possible locations for $x_{n+1}$ and $x_{n+2}$ .

So, let $A_{p,q}$ represent the transformation matrix when $L(x_{n+1})=p$ and $L(x_{n+2})=q$ and p<q

.

$A: \begin{cases}q<3i: \quad A_i = 1\\ p>3i: \quad A_i = 1\\ \end{cases}$

If p<3i<q

then $AM_{(3i,j)} = N_{(3i,j)}$ . There is a 4th case which is a subset of the 3rd case above, and that is when p< 3i < q

and either |p-3i|=1

or

. In this case, $AM_{3i, j} =-1$ .

I can't take it from here. I don't know whether it goes anywhere from here, and I apologize again for my severe shortcomings in linear algebra. I hope it gives someone some ideas on another tack.

sean39 · **Posted:** Wed, 18 Mar 2009 01:41:49 UTC

I have a feeling that there is no simple solution, but that possibly the probability approaches 1/2 as $n \to \infty$ . I wonder if that is any easier to prove.

Denis · **Posted:** Wed, 18 Mar 2009 14:35:19 UTC

Looking at 3 jars, 3 colors (color1 = 1,2; color2 = 3,4; color3 = 5,6):
as example, if 4,3,6,1,2,5 are random results, then Jars A,B,C = 4-3, 6-1, 2-5;
can be rearranged as 1-6, 2-5, 3-4.
There's 15 possible results:
12 34 56 yes
12 35 46 yes
12 36 45 yes
13 24 56 yes
13 25 46 no
13 26 45 no
14 23 56 yes
14 25 36 no
14 26 35 no
15 23 46 no
15 24 36 no
15 26 34 yes
16 23 45 no
16 24 35 no
16 25 34 yes

7 yes, 8 no; so probability = 7/15

The "1" being fixed, we have 3 combos for each of others:
so (c = nunber of candies) total combos = 3(c - 1)

Works similarly for our 12 candies: 945(c - 1) = 10,395 total combos.

BUT how is the 945 arrived at?

If we figure that out, we're still in trouble:
how is the 4355 "yes cases" arrived at?

Opalg · **Posted:** Wed, 18 Mar 2009 18:13:31 UTC

My approach to the "pairs" problem was to look at this situation: Suppose that you have m+n jars, 2m+n colours and 2m+2n candies. There are n pairs of candies and 2m single candies. Each pair has one of the n colours; each of the 2m single candies has a different colour. The candies are dropped at random in the jars, 2 in each jar, and P(m,n) denotes the probability that NO jar contains two candies of the same colour.

Thinking about what happens when two random candies are dropped into the first jar, you get the recurrence relation

$P(m,n) = \frac{2n(n-1)P(m+1,n-2)\; +\; 4mnP(m,n-1)\; +\; m(2m-1)P(m-1,n)} {(m+n)(2m+2n-1)}$ .

(The three terms on the right correspond to the three possibilities for the two candies: (a) they come from distinct pairs, (b) one comes from a pair and the other is single, (c) both are single.)

This recurrence relation satisfies the boundary conditions P(m,0)=1 (because if all the candies have different colours it's obviously impossible for a jar to contain two of the same colour), and P(0,1)=0 (because then there are two candies, both having the same colour, and only one jar to put them in ...).

Applying the recurrence relation recursively, we get $P(0,6) = \frac{10}{11}P(1,4) = \frac1{11\times9}\bigl(48P(2,2) + 32P(1,3) + 2P(0,4)\bigr) = \ldots$ .

After a few more recursions, the result comes out as $\frac{6040}{1\times3\times5\times7\times9\times11}$ .

The pattern for the denominator is clear enough (!), but I don't see much hope of finding a simple pattern for the numerator.

(The original problem asked for 1 â€“ P(0,6), but I think it's more natural to look at the case where there are no jars with candies of the same colour.)

aswoods · **Posted:** Wed, 18 Mar 2009 18:33:44 UTC

Put a pair of candies in one jar, then fill the rest randomly.

There are 6 ways to choose a pair of candies, and 6 ways to choose a jar. Then there are 10!/2^5 ways to fill the rest.

But this counts too many, because there might be two pairs. So subtract the following number...

There are 6.6.5.5/2! ways to put two pairs of candies in two different jars. Then there are 8!/2^4 ways to fill the rest.

But this counts too many, because there might be three pairs. So subtract the following number...

There are 6.6.5.5.4.4/3! ways to put three pairs of candies in three different jars. Then there are 6!/2^3 ways to fill the rest.

But this counts too many... et cetera.

$\frac{6^2}{1!}\cdot\frac{10!}{2^5}-\frac{6^25^2}{2!}\cdot\frac{8!}{2^4}+\frac{6^25^24^2}{3!}\cdot\frac{6!}{2^3}-\frac{6^25^24^23^2}{4!}\cdot\frac{4!}{2^2}+\frac{6^25^24^23^22^2}{5!}\cdot\frac{2!}{2^1}-\frac{6!6!}{6!}\cdot\frac{0!}{2^0}$

Answer: 3 135 600.

Divide by 7 484 400 to get 0.41895141895...

Denis · **Posted:** Wed, 18 Mar 2009 22:28:50 UTC

aswoods wrote:

> There are 6 ways to choose a pair of candies, and 6 ways to choose a jar.
WHY choose a jar?

> Answer: 3 135 600.
> Divide by 7 484 400 to get 0.41895141895...
Same as what we've already got: 871/2079 (from 4355/10395)

S.O.S. Mathematics CyberBoard

Try this!

Who is online