Combinatorics and Probability Combination Question

GRE Quant Problem Solving
1

Screenshot 2023-12-23 at 04.22.47
Screenshot 2023-12-23 at 04.22.472388×930 177 KB

Since this problem was discussed a lot in the recent 10-Questions Quiz, I’ve tried to put forward a conceptual brute-force approach by @gregmat, and a generalization explained by @kautsgre.

The brute force approach

Let’s see how many permutations we get.
Since we have 4 distinct dishes, the number of permutations is 4! = 24.

Column A Column B Column B Column D
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA

Out of these, which permutations get at least one dish at the correct place?

Column A Column B Column C Column D
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA

What do you notice about the non-highlighted permutations?

They serve all dishes at the wrong places, exactly what we need to count to get the probability!

  • Here, we use a concept called derangements.
  • Derangement means a permutation in which no element is in its original/fixed place.
  • In our assumption it means- A cannot be at position 1, B cannot be at position 2, C cannot be at position 3 and D cannot be at position 4.
  • Clearly, we get 9 derangements.

The required probability is

\frac{\text{Number Of Derangements}}{\text{Total Number Of Permutations}} = \frac{D_n}{n!} = \frac{9}{4!} = \frac{9}{24} = \frac{3}{8}

Generalization if you need to work with larger numbers

Here, we use the derangement formula, described by @kautsgre on Combinatorics question Using Sets

\frac{D_n}{n!} = \frac{n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}}{n!} = \sum_{i=0}^{n} \frac{(-1)^i}{i!}
D_4 = 4! \sum_{i=0}^{4} \frac{(-1)^i}{i!} = 24 \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right)

Breaking it down step by step:

D_4 = 24 \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right)

Combine the terms:

D_4 = 24 \left(\frac{24 - 24 + 12 - 4 + 1}{24}\right)

Simplify:

D_4 = 24 \left(\frac{9}{24}\right)

Cancel out the common factor:

D_4 = 9

The required probability is

\frac{\text{Number Of Derangements}}{\text{Total Number Of Permutations}} = \frac{D_4}{4!} = \frac{9}{4!} = \frac{9}{24} = \frac{3}{8}

Thanks for reading!

1 Like
2

Beautiful formatting and very nice write-up! This is an awesome post.

1 Like