Line of boys and girls
Thread Rating:
July 15th, 2015 at 2:10:11 PM
permalink
I came across this problem on the Ask Dr. Math website, and frankly I was appalled by the answer given which has been up since 1996. After a discussion of the theory of runs and occupancy problems, it fails to even get a numeric answer saying it would involve "a lot of rather tedious work". I hope you can easily get the exact answer in your head. No knowledge of occupancy problems required.
Note that it isn't asking for the average number of people standing next to someone of the opposite sex, though that would be another easy question. Instead we want the average number of spaces between people where a boy and a girl come together.
Quote:Suppose that 7 boys and 13 girls line up in a row. Let S be the number
of places in the row where a boy and a girl are standing next to each
other. For example, for the row GBBGGGBGBGGGBGBGGBGG we have S = 12.
If all possible orders of these 20 people are considered, what is the
average value of S? Can you generalize this result to a group of m
boys and n girls?
Note that it isn't asking for the average number of people standing next to someone of the opposite sex, though that would be another easy question. Instead we want the average number of spaces between people where a boy and a girl come together.
July 17th, 2015 at 12:40:18 PM
permalink
I've yet to find the clever, "easily in your head" solution, but here is my dumb tedious solution.
The highest possible value of S is 14.
E(S) = P(S=1) + 2*P(S=2) + ... + 14*P(S=14) = sum from k=1 to k=14 of k*P(S=k)
Let ((n,r)) = n multichoose r = C(n+r-1, r)
N(1) = 2
N(2) = 6+12
N(3) = 2*6*((2,11))
N(4) = 6*((3,10)) + 12*((3,4))
N(5) = 2*C(6,2)*((3,10))
N(6) = C(6,3)*((3,10)) + C(12,3)*((3,4))
N(7) = 2*C(6,3)*((4,9))
N(8) = C(6,4)*((4,9)) + C(12,4)*((4,3))
N(9) = 2*C(6,4)*((5,8))
N(10) = 6*((5,8)) + C(12,5)*((5,2))
N(11) = 2*6*((6,7))
N(12) = ((6,7)) + C(12,6)*6
N(13) = 2*C(12,6)
N(14) = C(12,7)
For the P's we divide each by C(20,7). After doing that and taking the weighted average, I get E(S) = 9.1
Not sure if 9.1 is an answer you could get in your head, so I may have messed up somewhere. Edit: and if I were told 9.1 was wrong, my next guess would be exactly 9.
Edit #2 -- my P's add to 1, so that increases my confidence in 9.1
The highest possible value of S is 14.
E(S) = P(S=1) + 2*P(S=2) + ... + 14*P(S=14) = sum from k=1 to k=14 of k*P(S=k)
Let ((n,r)) = n multichoose r = C(n+r-1, r)
N(1) = 2
N(2) = 6+12
N(3) = 2*6*((2,11))
N(4) = 6*((3,10)) + 12*((3,4))
N(5) = 2*C(6,2)*((3,10))
N(6) = C(6,3)*((3,10)) + C(12,3)*((3,4))
N(7) = 2*C(6,3)*((4,9))
N(8) = C(6,4)*((4,9)) + C(12,4)*((4,3))
N(9) = 2*C(6,4)*((5,8))
N(10) = 6*((5,8)) + C(12,5)*((5,2))
N(11) = 2*6*((6,7))
N(12) = ((6,7)) + C(12,6)*6
N(13) = 2*C(12,6)
N(14) = C(12,7)
For the P's we divide each by C(20,7). After doing that and taking the weighted average, I get E(S) = 9.1
Not sure if 9.1 is an answer you could get in your head, so I may have messed up somewhere. Edit: and if I were told 9.1 was wrong, my next guess would be exactly 9.
Edit #2 -- my P's add to 1, so that increases my confidence in 9.1
July 17th, 2015 at 3:11:10 PM
permalink
9.1 is correct. The in-your-head solution only requires applying something very basic.
July 17th, 2015 at 11:23:59 PM
permalink
This feels like there should be a reduction to some bit-twiddling hack but I can't put my finger on it right now. Something about the number of flipped digits. I want to say the given string GBBGGGBGBGGGBGBGGBGG would have a "dual" of 1010011110011110110 (length 19, where 1s represent the sought-after pairs) -- but I don't know if that's at all relevant.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
July 18th, 2015 at 11:03:58 AM
permalink
The probability that a space has a boy and a girl adjacent to it is 7/20 * 13/19 * 2, where we multiply by 2 since they can be BG or GB. Since there are 19 spaces, just multiply that by 19 to get 7*13/10 = 9.1.
I think many people have an aversion to this solution because they are concerned about dependencies. They are irrelevant since the expected value of a finite sum of random variables is always the sum of expected values regardless of whether the random variables are independent or dependent.
In this case, each space corresponds to a random variable which counts the number of B and G pairs adjacent to it, so it is either 0 or 1. It is 1 with probability 7/20 * 13/19 * 2, so that is its expected value. We have N=19 of these random variables with this same expected value, so the expected value of their sum is 19 times this expected value which is just the sum of the probabilities. For a general number of boys B and girls G, this comes to 2BG/(B+G) which is the harmonic mean of the numbers of boys and girls.
Whenever a problem asks for the expected value of a number of something, bells should go off telling you to consider adding probabilities. In fact, an alternative definition of expected value for a random variable N that takes on non-negative integer values is
The idea here is that each value contributes 1 to the count the fraction of the time N is greater than it. For example, to get the average number of times you must flip a coin to get heads, you can say you will always flip at least 1 time, then 1/2 the time you will flip at least 1 more time, 1/4 of the time you will flip at least 1 more time, etc. Then 1 + 1/2 + 1/4 + ... = 2.
The version for a continuous non-negative random variable is
The boy girl solution doesn't use these last 2 definitions of expected value, but it does use the idea of adding probabilities of random variables that each contribute a value of 1 some fraction of the time in order to get the expected value of a number of something.
Here is another problem using this concept. You have a box with N pieces of rope. You randomly select 2 ends, and tie them together. You repeat this N times so that all the ends are tied. What is the average number of loops you make?
July 18th, 2015 at 2:14:19 PM
permalink
To clarify, a loop is one or more pieces with the ends tied together? Or is it just a single piece tied to itself? E.g., if there are 4 pieces labelled 1 through 4, I could have knots at 11 23 34 42. Is that one loop or two?Quote: BruceZHere is another problem using this concept. You have a box with N pieces of rope. You randomly select 2 ends, and tie them together. You repeat this N times so that all the ends are tied. What is the average number of loops you make?
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice."
-- Girolamo Cardano, 1563
July 18th, 2015 at 2:30:46 PM
permalink
Quote: MathExtremistTo clarify, a loop is one or more pieces with the ends tied together? Or is it just a single piece tied to itself? E.g., if there are 4 pieces labelled 1 through 4, I could have knots at 11 23 34 42. Is that one loop or two?
A loop is one or more pieces with the ends tied together. Your example would be 2 loops.
July 19th, 2015 at 8:04:03 AM
permalink
Yeah I knew it had something to do with , but at first I was chasing a red herring.
Here's what finally came to me before reading Bruce' solution. Not quite as good, but much better than what I did before, and possible in your head.
linearity of expectations
Here's what finally came to me before reading Bruce' solution. Not quite as good, but much better than what I did before, and possible in your head.
Consider the spaces between and around the girls: 8 in total.
If a boy is placed between 2 girls (there are 6 ways to do that) then that creates 2 of the spaces whose average we want. If a boy is placed next to an end girl (there are 2 ways to do that) then that creates 1.
What's the probability that at least one boy is in a given spot?
1 - P(none) = 1 - ((7,13))/((8,13)) = 1 - C(19,6)/C(20,7)
You can do C(19,6)/C(20,7) in your head: it reduces to 7/20
So the average is 14 * 13/20 = 182/20 = 9.1
If a boy is placed between 2 girls (there are 6 ways to do that) then that creates 2 of the spaces whose average we want. If a boy is placed next to an end girl (there are 2 ways to do that) then that creates 1.
What's the probability that at least one boy is in a given spot?
1 - P(none) = 1 - ((7,13))/((8,13)) = 1 - C(19,6)/C(20,7)
You can do C(19,6)/C(20,7) in your head: it reduces to 7/20
So the average is 14 * 13/20 = 182/20 = 9.1
July 27th, 2015 at 7:50:19 AM
permalink
is this not counting over-lapping B/G or G/B couples?Quote:For example, for the row GBBGGGBGBGGGBGBGGBGG we have S = 12.
why count this way?
(extra credit) is this important in your field of work? (or field of play)
here is how i see this (left to right)
GB-BG-G-GB-GB-GG-GB-GB-G-GB-GG
S=7
right to left
GB-BG-GG-BG-BG-GG-BG-BG-G-BG-G <<< start here
S=7
i also see overcast skies
and marshmallow pies :)
I Heart Vi Hart
