Simple combinatorics problem - assigning people to groups

Question

$20$ people that A, B and C belong to are to be randomly seperated in groups of 4. I have a few questions about this problem:

Q1: What is the probability, that A, B and C place in the same group?
My intuition would be, that the person A has a $4/20=1/5$ chance to land in group 1 and then person B has a $3/19$ chance to land in the same group and finally person C has a $2/18$ chance to do the same. Because there are $5$ groups, this means that $\mathbb{P}(Q1)=5\frac{1}{5}\frac{3}{19}\frac{2}{18}=\frac{1}{57}$.

Q2: What is the probability that they all are placed in different groups?
Place person A in group $a$ (probability $1/5$). Then place person B in group $b\neq a$ - probability $4/19$. Finally place person C in group $c\notin\{a,b\}$ - probability $4/18$. There are $\binom{5}{3}$ ways to choose $a,b,c$, so $\mathbb{P}(Q2)=\binom{5}{3}\frac{1}{5}\frac{4}{19}\frac{4}{18}$
This somehow seems wrong to me, because it does not account for the other $17$ people.

Q3: What is the conditional probability, that A,B,C land in different groups if it is already known that two of them are in different groups?
This one I really struggle with. My attempt: Because there are three groups to choose from and $18$ people to match, I think that $\mathbb{P}(Q3)=3\frac{4}{18}$.

Please check my solutions and tell me what is wrong.

EDIT: Thank you to everyone for the discussion and solutions, especially to @chrslg for even throwing together a little simulation. Also, Q3 is for sure related to conditional probability, so $\mathbb{P}(Q3)=\frac{\mathbb{P}(Q1)}{1-\mathbb{P}(Q2)}$, as pointed out by you all.

Answer 1

$\require{cancel}$

Your first answer is correct, but your second isn't.

What I consider the simplest approach is given below.

Consider $20$ slots in $5$ groups of $4$,

$\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}$

• (1) The first person can be anywhere, the remaining two can be placed in the same group with $Pr =\frac{3}{19}\frac{2}{18} = \frac1{57}$

• (2) The first person can be anywhere, the other two can be placed in different groups with $Pr = \frac{16}{19}\frac{12}{18} = \frac{32}{57}$

• (3) Two blocks are already occupied, $12$ "good" slots are available, $\cancel{Pr =\frac {12}{18}}$

Correction to part (3)

Since this is a conditional probability question,

$Pr = \frac{All \;in \;different\; groups}{All \;not\; in\; same\; group} = \frac{32}{57}\big/\frac{56}{57} = \frac47$

Answer 2

To avoid using comments, to heavily, I add my views in an answer.

Q1) I am ok with already, twice, given answers.

Q2) I am in agreement with true blue anil. Although I failed to find his elegant way of modeling it, my inelegant reasoning lead to the same result. And so did the monte-carlo simulation I ran.

Q3) I understand the question as "you already know that 2 of A,B,C are in different group. What is the probability that all 3 are in different group". So, calling $k$ the number of groups among which A,B and C are distributed $$ P[k=3 | k\geq 2] = \frac{P[k=3\mbox{ and } k\geq 2]}{P[k\geq 2]} $$ Here, since there is no cases where all 3 of A,B,C are in different groups, but we can't find 2 of them that are in different groups (in other words, where $k=3$ but $k<2$), the computation simplify a little bit $$ P[k=3 | k\geq 2] = \frac{P[k=3]}{P[k\geq2]} $$ @trueblueanil already computed $P[k=3] = \frac{16×12}{19×18}$

We just need to compute $P[k\geq2]$. In fact, we don't really need to (and that a virtue of writing a proper answer, because I only see that now. I wasn't seeing it while arguing in comments). Because we know that k has to be either 1, 2 or 3. And we know $P[k=1]$. That is the answer to Q1. $$ P[k=1] = \frac{3×2}{19×18} $$ Hence $$ P[k\geq 2] = 1-P[k=1] = 1-\frac{3x2}{19×18} = \frac{19×18-3×2}{19×18} $$ So, answer to Q3 is $$ P[k=3 | k\geq 2] = \frac{P[k=3]}{P[k\geq 2]} = \frac{ \frac{16×12}{19×18} }{ \frac{19×18-3×2}{19×18} } = \frac{16×12}{19×18-3×2} $$ Since $19×18-3×2 = 16×18+3×16 = 336 $$ we are back to what I said in comments. Except that this time, I am pretty sure that this is the way it was intended by the teacher. Q3 answer is just a combination of Q1 and Q2. Classic teacher trick (being one myself...).

All we had to do to answer Q3 was $\frac{\mbox{answer to q2}}{1-\mbox{answer to q1}}$

My initial reasoning was, from true blue anil slot system: arbitrarily choosing to place A in the first slot (we can do so. It is just a naming choice), we have $16$ ways to place B, and $12$ ways to place C to have all 3 in different groups. And to enumerate slots positioning leading to at least 2 of A,B,C in different groups, either:

• B is in a different group than A (16 slots for B) and then C can be in any other slot
• B is in the same group as A (3 other slots for B). Not a problem, but then C needs to be in another group (16 slots)

Now, since I mentioned Monte-Carlo, here is my C code

#include <stdio.h>
#include <stdlib.h>

int avail[20]; // Available slots (at first all 20)
int nd=20;     // Number of available slots
int ga,gb,gc;  // Groups for A, B, and C

// Reset (nobody is placed)
void init(){
    // Just for debug, I choose not to name any slot 0. So if there is a 0, we have a bug
    // Initially all slots 1,2,3...,20 are available
    for(int i=1; i<=20; i++){
        avail[i-1]=i;
    }
    nd=20; // That is 20 of them
    // A, B, C are placed nowhere
    ga=-1;
    gb=-1;
    gc=-1;
}
// Choose a person for each slot
void distrib(){
    // For all group, for all slot in all group
    for(int g=0; g<5; g++){
        for(int i=0; i<4; i++){
            // I choose a person among the nd still available
            int p=random()%nd;
            // To simplify a bit, I arbitrarily choose to place A (person 1) into 1st slot of 1st group
            // This is just a naming choice, so it changes nothing
            if((g==0) && (i==0)) {
                p=0;
                ga=g;
            }
            // If perso 2 (B) is chosen, store group in gb
            if(avail[p]==2) gb=g;
            // Likewise for (C)
            else if(avail[p]==3) gc=g;
            // At first I was litteraly distributing number into 5 arrays of 4 slots
            // But turns out I never used "group" in the rest of the code, so uneeded
            // group[g][i]=disp[p];

            // p is not available any more. The last element from avail[0..nd[ takes is place 
            // and we have one less element in avail[0..nd[
            // (Just a fast way to remove an element from an array when we don't care of order)
            avail[p]=avail[nd-1];
            avail[nd-1]=0;
            nd--;
        }
    }
}

int main(){
    // Monte-Carlo simulation
    long long n=0;
    long long ndiff=0;
    long long nsame=0;
    long long nk2=0;
    for(;;){
        // Reset and redistribution persons
        init();
        distrib();
        // Total number of cases
        n++;
        // Cases for which all are in the same group
        if((gb==ga) && (gc==ga)) nsame++;
        // Cases for which all 3 are in different groups
        if(ga!=gb && ga!=gc && gb!=gc) {
            ndiff++;
        }
        if(ga!=gb || ga!=gc || gb!=gc) nk2++;
        if(n%10000) continue; // Just to avoid having 99% of CPU only for writing result
        // Print result
        printf("n=%-8lld  same=%lld %7.4f%% diff=%lld %7.4f%%  cond=%lld/%lld %7.4f%%\r", n, nsame, (100.0*nsame)/n,
                ndiff, (100.0*ndiff)/n, ndiff, nk2, (100.0*ndiff)/nk2);
    }
}

Let me know if you see any reasoning error in this (naive) simulation. (I know, there are lot of possible simplification. Some of them, just because I missed them. Some others because when I write such Monte-Carlo to check probability I avoid thinking too much, to be sure not to include bias)

But well, that code is fast enough so that I need 64 bits integer to hold number of cases. And it leads to the same result I am defending.

Answer 3

Your answer to the first question is correct.

Q2: Any particular outcome has probability $\frac{4!^5}{20!}$, where $n!=n\cdot(n-1)\cdots 1$ is the factorial. The reason is that no matter what person you put in which group, you will fill up the 4 spots in the 5 groups one by one. Let's assume that A,B,C are the first three persons. Let us also fix groups $a,b,c$. Now, we can iterate through all possibilities where A ends up in $a$, B in $b$ and C in $c$. Since the probability of each outcome is the same, and equal to $\frac{4!^5}{20!}$, we only need to count the possible assignments of the remaining $17$ persons to groups, that is we have the letters $d$, $e$ four times, and the others three times, yielding $\binom{17}{3,3,3,4,4}=\frac{17!}{3!^34!^2}$, using the multinomial coefficient. Summing over these outcomes gives $\binom{17}{3,3,3,4,4}\frac{4!^5}{20!}=\frac{4^3}{20\cdot 19\cdot 18}$. Next, we sum over the choice of groups. Now, we have to choose one group for A, one for B and one for C, yielding $\frac{5\cdot 4\cdot 3\cdot 4^3}{20\cdot 19\cdot 18}=\frac{32}{57}$.

Q3: There are several ways to consider to think of the conditional probability, in case of doubt one approach is always $P(A|B)=P(A\cap B)/P(B)$. In this case, the probability that all three land in different groups, and two of them land in different groups, well, is the probability that all three land in different groups (the former event is a subset of the latter, hence the intersection is the former). But this probability is exactly the probability from Q2. On the other hand, the complement of the event that there exist two that are in different groups, is the event that all three are in the same group, the event from Q1. Hence, the probability is $\mathbb P(Q2)/(1-\mathbb P(Q_1))=\frac{57}{56}\frac{32}{57}=\frac{4}{7}$.