What is the probability?
1. Kevin has four red marbles and eight blue marbles. He arranges these twelve marbles randomly, in a ring. Determine the probability that no two red marbles are adjacent.
2. Six people in chemistry class are going to be placed in three groups of two. The teacher asks each student to write down the name of that student’s desired partner. If each student picks a favorite partner at random, what is the probability that there is at least one pair of students who have picked each other?
For the first problem, the objects are arranged in a ring, not a linear configuration. I assume the problem does take invariance under rotation into account.
I'll throw in my thoughts on the first problem:
If there are twelve fixed (and distinct) spots around the ring, we cannot assume invariance under rotation anymore, and 7/33 looks right to me.
If we are to put the 12 objects on the continuous circumference, I think the assumption of rotational equivalences is necessary, and Duke's answer (and my original answer) of 10/43 looks correct.
Is my argument sound? I didn't realize whether we are treating the ring as a continuous circumference will make such a difference.
By the way this is problem 6 at
- DukeLv 710 years agoFavourite answer
I do not agree with the answers to the first question. Under the assumption that two ring arrangements of 4 red indistinguishable and 8 blue indistinguishable marbles are identical under rotation only (i.e. the reverse side of the ring is considered a different arrangement, treating it like a coin) I think the required probability is 10/43, as we have discussed in our private emails (without distinguishing front and back sides, i.e. left from right neighbors it would be 8/29).
Follow the link below to see an illustration:
Each ring arrangement can be described as a quadruple
'abcd' /a, b, c, d = 0, 1, 2, . . , 8; a + b + c + d = 8/
meaning 'a' blue marbles between 1st and 2nd red, 'b' blue between 2nd and 3rd red, 'c' blue between 3rd and 4th red, 'd' blue between 4th and 1st red (clockwise). For example
0116 means the string -R-R-B-R-B-R-B-B-B-B-B-B- with connected ends (2nd row, 3rd from left on the picture). Cutting the ring between any 2 marbles and rectifying the string we get an arrangement of the 12 marbles in a row. Turning the above ring we get 6110 - its mirror image - another arrangement according the initial agreement.
The following table contains all possible 'lexicographical partitions' of 8 into 4 addends, the number of corresponding ring arrangements and how many row arrangements generates each of them (shown in parentheses along with the symmetry type of each ring on the picture):
0008 - 1 ring arrangement, generates 12 row arrangements;
0017 - 3 ring arrangements, generates 3*12 row arrangements;
0026 - 3 ring arrangements, generates 3*12 row arrangements;
0035 - 3 ring arrangements, generates 3*12 row arrangements;
0044 - 2 ring arrangements, generates 12 + 6 row arrangements;
0116 - 3 ring arrangements, generates 3*12 row arrangements;
0125 - 6 ring arrangements, generates 6*12 row arrangements;
0134 - 6 ring arrangements, generates 6*12 row arrangements;
0224 - 3 ring arrangements, generates 3*12 row arrangements;
0233 - 3 ring arrangements, generates 3*12 row arrangements;
1115 - 1 ring arrangement, generates 12 row arrangements;
1124 - 3 ring arrangements, generates 3*12 row arrangements;
1133 - 2 ring arrangements, generates 12 + 6 row arrangements;
1223 - 3 ring arrangements, generates 3*12 row arrangements;
2222 - 1 ring arrangement, generates 3 row arrangements;
40 ring arrangements, generating 12 row arrangements each;
2 ring arrangements, generating 6 row arrangements each;
1 ring arrangement, generating 3 row arrangements;
or 40*12 + 2*6 + 1*3 = 495 = C[12, 4] row arrangements.
The favorable cases (10) for the required probability are on the last 2 rows on the picture, what explains my answer 10/43 for the first question. I was somewhat surprised to read another answer (7/33) on a reliable site and as a check tried similar approach to analyze the easier cases:
1 red + 2 blue:
2 - 1 ring, generating 3 = C[3, 1] row arrangements;
2 red + 4 blue:
04 - 1 ring, generating 6 row arrangements;
13 - 1 ring, generating 6 row arrangements;
22 - 1 ring, generating 3 row arrangements;
(6 + 6 + 3 = C[6, 2])
3 red + 6 blue:
006 - 1 ring, generating 9 row arrangements;
015 - 2 rings, generating 2*9 row arrangements;
024 - 2 rings, generating 2*9 row arrangements;
033 - 1 ring, generating 9 row arrangements;
114 - 1 ring, generating 9 row arrangements;
123 - 2 rings, generating 2*9 row arrangements;
222 - 1 ring, generating 3 row arrangements;
(9 + 18 + 18 + 9 + 9 + 18 + 3 = 84 = C[9, 3])
P.S. (Note to Gianlino) I do not understand what You have written: "You have a ring with 12 spots. You put 4 red marbles and 8 blue marbles at random. That will give you 12 Choose 4 possibilities..." Take a ring with 3 spots and put 1 red and 2 blue marbles at random. How many ring arrangements are possible? Are they C[3, 1] = 3?
P.S.(2) The number 43 of necklaces with 4 + 8 marbles is given in OEIS:
/value #8, starting from #0, see also COMMENTS Section and the generating function below on the page/
Now I hope this reference is sufficiently convincing.
P.S.(3 - Final) In my opinion the words "...He arranges these twelve marbles randomly, IN A RING..." along with the 1st clarification in the Additional Details imply the number of possible cases is the number of ring arrangements (necklaces).
Since I may be wrong, next time I am going to ask Kevin before answering.Source(s): http://en.wikipedia.org/wiki/Necklace_%28combinato... http://mathworld.wolfram.com/Necklace.html
- 10 years ago
Looks like this problem is getting lively.
For problem 1, I get 35/165 or 7/33
Pick any particular place on the chain for the first red marble without loss of generality. There are now 9 potential spots to fill in the last 3 red marbles. Pretty easy to figure 35 possible combination with a space between each marble
= ( (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) +1 )
= 1/6 ( 5³ + 3 * 5² + 2* 5)
There are also 11 different spots that the last 3 marbles could be dropped into. This works out to be 165 combination or
=1/6 ( 9³ + 3 * 9² + 2* 9)
Haven't even thought about #2 yet ... got go watch the baseball game and take care of the kids. But I might come back this evening if I'm not too tired.
- gianlinoLv 710 years ago
For 1/ you can look at this very similar question.
edit Totally disagree with M3.
1/ you should get 8 C 4 / 12 C 4, that is
8*7*6*5 / 12*11*10*9 = 7*240 / 120*99 = 14 / 99.
2/ is as simple as it first appears =)
edit: for 1/ I forgot a factor 8/12 in the denominator. So the answer is 3/2 * 14/99 = 7/33, as found by Ericlord.
edit for 2. There are 15 pairs; Each has a probability 1/25 to be matched. So the expected number of matched pairs 15/25 = 3/5. Let p_x, x = 1,2,3 be the probability that exactly x pairs are matched. Hence p_1 + 2p_2 + 3p_3 = E(x) = 3/5. You are looking for p = p_1 + p_2 + p_3 = 3/5 - p_2 - 2p_3.
p_3 = (1/25)^3* 6!/3!(2!)^3 = 15 /25^3 = 3/5^5
p_2 = (1/25)^2*(24/25)*3*15 = 216/5^5
p = 3/5 - 216/5^5 - 2*3/5^5 =
(1875 - 216 - 6)/3125 = 1653 /3125.
Edit I disagree with Duke's answer but I think we just did not tried the same problem.
You have a ring with 12 spots. You put 4 red marbles and 8 blue marbles at random. That will give you 12 Choose 4 possibilities. Now the question is that "no two red marbles are adjacent." ok you have N possibilities. Divide by N by 12 / Choose 4 and you get your probability.
The ring structure is here to make a distinction with a row of 12 but noone ever spoke of invariance of any kind. It is just the question of what is adjacent to what which marginally changes from the ring case to the linear case.
edit Oh actually, the asker did speak of invariance, but just as some kind of personal assumption. Noone in his source does.
to Duke exactly. Yes. The guy who is going to put down the marbles does not even know that rotations exist. It's not like choosing from various arrangements. You have a guy to whom you asked to put 12 marbles around who knows what, with the non adjacent requirements. But he forgets. What are the chances you'll yell at the end?
- siamese_scytheLv 710 years ago
Might as well comment on this. Hopefully I don't make an error and add to confusion.
1) It is valid to consider 495 equally likely arrangements as has been done by others, noting that some of these arrangements are equivalent up to rotation. This means: If we consider all distinct arrangements up to rotation, we may have difficulty using these counts for probability because *they are not all equally likely* given a random placement of marbles.
Now, let's simplify a bit and consider them placed linearly. Using visual aids,
| B | B | B | B | B | B | B | B |
Considering just the linear case, there are C(9,4) = 126 arrangements in which no two red marbles are adjacent. But of course we must take out those that have marbles in both the first and last positions. There are C(7,2) = 21 of these. So in the end we get (126-21)/495 = 7/33, in agreement with some previous answers.
2) Here there are 5^6 distinct possibilities, all equally likely. I think we can count directly, rather than counting the opposite of what we want and taking the complement. We will use principle of inclusion-exclusion. Consider selecting any pair and making them choose each other. There are C(6,2) = 15 ways to choose the pair, and 1 way they can choose each other. For each of these 15 ways, we have 5^4 = 625 ways the other people can choose. But of course if we do 15*5^4 we count duplicates. So, select two pairs and make them choose each other. There are C(6,4) * C(4,2) / 2 = 45 ways to do this. And the other people can choose in 5^2 = 25 ways. Now finally let's make it so all three have chosen in pairs. There are 5*3*1 = 15 ways to break into pairs. So we have numerator
15*5^4 - (C(6,4) * C(4,2) * 5^2) + 5*3*1 = 8265
So we get probability 8265/5^6 = 1653/3125
which matches what bright s hell got.
- What do you think of the answers? You can sign in to give your opinion on the answer.
- ericlordLv 410 years ago
There are 12C4 = 495 possible arrangements (495 ways the four red marbles can be distributed in 12 positions). There are 12 arrangements in which all four red marbles are adjacent. 12x7 = 84 ways in which just three are adjacent (ie, 12 sets of three adjacent positions in the ring and in each case 7 positions for the remaining red marble). 12x7/2 = 42 arrangements with two adjacent pairs of red marbles, not adjacent to each other, and 12x(6+5+4+3+2+1) = 252 arrangements with one adjacent pair and the other two red marblesisolated by adjacent blue ones. Altogether, then, we have 12 + 84 + 42 + 252 = 390 arrangements in which two red marbles are adjacent.
Therefore the probability that NO two red marbles are adjacent is 1 - 390/495 = 7/33.
Second question: if the students each choose their *favorite* partner, the situation is NOT random. However, if they really choose randomly, the question is interesting but too difficult for me - I give up...
- Vikram PLv 510 years ago
1) It's 7/33.
Number of distinct ways to arrange the marbles in a row: 12! / (8! * 4!) = 495
Now we want to have at least 1 blue marble in between any red marbles, we can think a red-blue pair as one marble with red on left & blue on right of the pair. Thus we have 8! / (4! * 4!) = 70 ways to arrange the marbles.
If one red-blue pair is at the very right of the row then in this case the blue marble on the right can be transferred to the beginning of the line. we can have 7! / (4! * 3!) = 35 ways for one red-blue pair to be on the very right, hence there are 35 ways to transfer the blue marble, for a total of 70 + 35 = 105 ways to arrange 4 red marbles and 8 blue marbles in a row so that no two red marbles are together.
105 / 495 = 7/33
2) seems tricky to me, let's say we have A,B,C,D,E,F
A can select from 5 other persons however for B, if A has selected him he can not select A & him self so he has only 4 ways but if A has selected any player other then B then B can also select from 5 & so on. Will think more about it & come later.
Well for Q2 gianlino, bright as hell and siamese_scythe has got it right, I liked gianlino's explanation, which is somewhat easy to follow.
- Mugen is StrongLv 710 years ago
same assumption as M3, rotation as same but not reflection (unless the marbles are drilled and stringed to make a pearl-ish bracelet, so i can put it down in 2 ways).
n = 1
n[3,1] = 7
n[2,2] = 4
n[2,1,1] = 21
n[1,1,1,1] = 9
answer = 9/42 = 3/14
there will be no pair if their desire-arrows are in a loop; that they make sides of polygons, at least for the more "desirable" students.
3-gon = 4360 [including the double triangle config with 40 ways]
4-gon = 2160
5-gon = 720
6-gon = 120
= [5^6 - sum] / 5^6
Duke is right. i missed 1 arrangement.
my previous, incomplete n[1,1,1,1] = 9 came from these strings indicating the number of B between 2 R.
i missed the obvious 2222.
- sanLv 510 years ago
2)prob(atleast one pair)=1-prob(no pair)
A can select any one person from B,C,D,E,F.he has 5 ways.
B-->4ways (leaving one person who has selected B as his partner)
- Anonymous10 years ago
No 1: About 70%
No 2: About 90%
- Anonymous10 years ago