Where to sit?

A class of 30 students contains 15 boys and 15 girls. Their classroom has 15 desks, and exactly 2 students can sit at each desk.

At the start of lessons one morning, the 30 students go into their classroom and seat themselves randomly, so that all possible arrangements of pupils are equally likely. The expected number of girls who end up sitting at a desk with another girl can be written as a b \dfrac{a}{b} , where a a and b b are coprime positive integers. What is the value of a + b a+b ?


The answer is 239.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Mark Hennings
May 13, 2016

Suppose that the class consists of n n boys and n n girls and n n two-seater desks. For any 1 j n 1 \le j \le n , let X j X_j be the random variable which is equal to 1 1 if the j t h j^\mathrm{th} girl is sitting next to another girl, and equal to 0 0 otherwise. Thus the total number of girls who are sitting next to a girl is Y = X 1 + X 2 + + X n . Y \; = \; X_1 + X_2 + \cdots + X_n \;. Since all seating arrangements are equally likely, any particular student will have any of the other 2 n 1 2n-1 pupils as a desk partner with equal probability. Thus the probability that the j t h j^\mathrm{th} girl is sitting next to another girl is the probability that she has one of the remaining n 1 n-1 girls as a desk partner, out of the total number of 2 n 1 2n-1 possible partners, namely n 1 2 n 1 \frac{n-1}{2n-1} . In other words E [ X j ] = P [ X j = 1 ] = n 1 2 n 1 E[X_j] \; = \; P[X_j = 1] \; = \; \frac{n-1}{2n-1} for all 1 j n 1 \le j \le n , and hence the expected number of girls who are sitting next to another girl is E [ Y ] = E [ X 1 ] + E [ X 2 ] + + E [ X n ] = n × n 1 2 n 1 = n ( n 1 ) 2 n 1 E[Y] \; = \; E[X_1] + E[X_2] + \cdots + E[X_n] \; = \; n \times \frac{n-1}{2n-1} \; = \; \frac{n(n-1)}{2n-1} When n = 15 n=15 this expected value is 210 29 \frac{210}{29} , making the answer 239 \boxed{239} .

Congrats on posting your first problem! I'm now waiting for your problem in calculus!

Aditya Kumar - 5 years, 1 month ago

Can someone explain it to me? I still dont understand it ...

Johannes R - 5 years, 1 month ago

Log in to reply

Suppose one of the girls is called Ann. What is the probability that Ann is sitting next to another girl? You could imagine that Ann is the first one into the room. It does not matter where she sits, all that matters is which of the other 2 n 1 2n-1 students sits next to her. Since n 1 n-1 of these students are girls, the probability that Ann sits next to another girl is n 1 2 n 1 \frac{n-1}{2n-1} . The point is that this probability is the same for all the other girls too, so the probability that any one of the girls is sitting next to another girl is n 1 2 n 1 \frac{n-1}{2n-1} .

Now imagine that all the students have sat down, and the teacher asks the girls "Who is sitting next to another girl? Hands up". The quantity X j X_j is equal to 1 1 (with probability n 1 2 n 1 \tfrac{n-1}{2n-1} ) if the j j th girl has her hand up, and is equal to 0 0 (with probability n 2 n 1 \frac{n}{2n-1} ) if the j j th girl does not have her hands up. The total number of hands up is the sum X X of the quantities X 1 , X 2 , , X n X_1,X_2,\ldots,X_n .

But the expectation of X j X_j is E [ X j ] = 1 × P [ X j = 1 ] + 0 × P [ X j = 0 ] = P [ X j = 1 ] = n 1 2 n 1 E[X_j] \; = \; 1 \times P[X_j=1] + 0 \times P[X_j = 0] \; = \; P[X_j = 1] \; = \; \tfrac{n-1}{2n-1} It is a property of expectations that the expectation of a sum of random variables is equal to the sum of their expectations, so that E [ X ] = E [ X 1 ] + E [ X 2 ] + + E [ X n ] = n ( n 1 ) 2 n 1 E[X] \; = \; E[X_1] + E[X_2] + \cdots + E[X_n] \; = \; \frac{n(n-1)}{2n-1}

Mark Hennings - 5 years ago

Log in to reply

Thank you!!!

Johannes R - 5 years ago

@Mark Hennings I have conveyed Calvin Sir to give my mail to you. I didn't see the mail earlier.

Ishan Singh - 5 years ago

Hello Sir. This is unrelated, but can just wanted to inform that I've sent you an email regarding the paper and one other issue.

Ishan Singh - 4 years, 12 months ago

Log in to reply

@Mark Hennings The email I sent possibly didn't reach you (since it wasn't received by Calvin Sir too). Hence I have resent it. Please do reply when you get time. Thanks.

Ishan Singh - 4 years, 12 months ago
Abdul Fayeed
May 13, 2016

My solution is as following: The probability for a girl to sit on the first chair is 1/15, then there are 14 girls left. The probability for another girl to sit on the second chair is now 1/14, so the combined probability is 1/15 + 1/14 = 29/210, then a+b= 239. But my steps do not really obey the info given. I just neglect the information given above about the boys etc, just calculate randomly haha

What?! How is this a solution? ... You are required to find the expected value.....

Johannes R - 5 years, 1 month ago
Andreas Wendler
May 15, 2016

First we realize that number of desks with only girls must be equal to number of desks with only boys, named k. Then the density of the probability f(k) can be calculated:

f ( k ) = 15 ! 3 2 15 2 k ( 15 2 k ) ! ( k ) ! 2 30 ! f(k)=\frac{15!^{3}\cdot 2^{15-2*k}}{(15-2*k)!(k)!^{2}\cdot 30!}

For the expected number of girls we obtain: k = 0 7 f ( k ) 2 k = 7.24137931034483 \sum_{k=0}^{7}f(k)\cdot 2k= 7.24137931034483

With happiness we determine that this value can be written as 210 29 \frac{210}{29} resulting in solution 239 \boxed{239} .

Yes, this formula works. It is quite a challenge to show by this method that the expectation is precisely equal to 210 29 \tfrac{210}{29} , rather than checking that the expectation agrees with 210 29 \tfrac{210}{29} to 14 14 DP...

Mark Hennings - 5 years, 1 month ago

Log in to reply

I assume one should have to analyze the sum formula in a proper manner!?

Andreas Wendler - 5 years, 1 month ago

Log in to reply

Yes. Of course, for this problem we have a finite number of explicit terms to evaluate, and these could all be determined as fractions, and therefore the exact sum evaluated.

A more challenging combinatoric problem would be to generalize this result to 2 n 2n children, and show that k = 0 1 2 n 2 k ( n k k n 2 k ) 2 n 2 k ( 2 n n ) = n ( n 1 ) 2 n 1 \sum_{k=0}^{\lfloor \frac12n\rfloor} 2k \frac{{n \choose {k\;k\;n-2k}} 2^{n-2k}}{{2n \choose n}} \; = \; \frac{n(n-1)}{2n -1} where ( n k k n 2 k ) {n \choose k\;k\;n-2k} is the multinomial ( n k k n 2 k ) = n ! ( k ! ) 2 ( n 2 k ) ! {n \choose k\;k\;n-2k} \; = \; \frac{n!}{(k!)^2 (n-2k)!}

Mark Hennings - 5 years, 1 month ago

Log in to reply

@Mark Hennings Both these sums can be evaluated in almost the same manner as my solution here .

Ishan Singh - 4 years, 12 months ago

In fact, a true combinatorial proof of the identity I wrote consists of combining your argument (to generate the series) with mine (which evaluates it cheaply).

Mark Hennings - 5 years ago
Zhizhong Lin
May 25, 2020

Let I i I_{i} denotes the indicator variable: it's 1 if the i t h i^{th} table have two girls and 0 otherwise. Based on the question, we want to know i = 1 15 E [ 2 I i ] \sum_{i=1}^{15}E[2I_{i}] . Since E [ I i ] = C 15 2 C 30 2 = 7 29 E[I_{i}] = \frac{C_{15}^{2}}{C_{30}^{2}} = \frac{7}{29} , we have i = 1 15 E [ 2 I i ] = 15 × 2 × 7 29 = 210 29 \sum_{i=1}^{15}E[2I_{i}] = 15\times 2 \times \frac{7}{29} = \frac{210}{29} . Thus a + b = 210 + 29 = 239

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...