S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
It is currently Tue, 21 Oct 2014 11:20:01 UTC

All times are UTC [ DST ]




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Try this!
PostPosted: Sat, 14 Mar 2009 18:47:10 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 4261
Location: Ottawa Ontario
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?

_________________
I'm just an imagination of your figment...


Top
 Profile  
 
 Post subject: Re: Try this!
PostPosted: Sun, 15 Mar 2009 02:38:16 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Mon, 19 May 2003 19:55:19 UTC
Posts: 8131
Location: Lexington, MA
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: 6! 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\%



Top
 Profile  
 
 Post subject:
PostPosted: Sun, 15 Mar 2009 03:26:24 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 4261
Location: Ottawa Ontario
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:

_________________
I'm just an imagination of your figment...


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 17 Mar 2009 09:57:37 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sat, 7 Jan 2006 18:29:24 UTC
Posts: 1401
Location: Leeds, UK
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.


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 17 Mar 2009 20:02:14 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 4261
Location: Ottawa Ontario
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:

_________________
I'm just an imagination of your figment...


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 01:15:17 UTC 
Offline
Senior Member

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 x_2 in Jar 1, x_3 and x_4 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 i: \begin{cases}x_{i}=x_{i+1}: \quad 1\\ x_{i} \neq x_{i+1}: -1 \end{cases}

For even values of i: \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 |q-3i|=1. 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.


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 01:41:49 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sun, 22 Feb 2004 23:09:47 UTC
Posts: 651
Location: 40.47N 73.58W
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.

_________________
"If I have not seen as far as others, it is because giants were standing on my shoulders." - Hal Abelson


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 14:35:19 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 4261
Location: Ottawa Ontario
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?

_________________
I'm just an imagination of your figment...


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 18:13:31 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Sat, 7 Jan 2006 18:29:24 UTC
Posts: 1401
Location: Leeds, UK
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.)


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 18:33:44 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame
User avatar

Joined: Mon, 23 Feb 2009 23:20:33 UTC
Posts: 1049
Location: Adelaide, Australia
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...


Top
 Profile  
 
 Post subject:
PostPosted: Wed, 18 Mar 2009 22:28:50 UTC 
Offline
Member of the 'S.O.S. Math' Hall of Fame

Joined: Sun, 24 Jul 2005 20:12:39 UTC
Posts: 4261
Location: Ottawa Ontario
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)

_________________
I'm just an imagination of your figment...


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC [ DST ]


Who is online

Users browsing this forum: No registered users


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Contact Us | S.O.S. Mathematics Homepage
Privacy Statement | Search the "old" CyberBoard

users online during the last hour
Powered by phpBB © 2001, 2005-2011 phpBB Group.
Copyright © 1999-2013 MathMedics, LLC. All rights reserved.
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA