elementary combinatorial exam allocation problem

Question

For many it might be exam season at the moment, and this brainteaser came up in discussion (apologies if duplicate but couldn't find anything on the site thus far):

Problem:

I have $18$ days on which exams can take place, $6$ exams to take, $2$ exam slots per day (AM/PM). Only one exam is allowed per slot, allocation is random. What is $p:=\mathbb{P}(2$ days will have $2$ exams on them$)$?

Apologies if this is too elementary, however barely did any combinatorics when studying aeons ago, (more analysis/algebra based), so very prone to making errors hence would be grateful if 'guess' could be sanity checked! Find it hard to inject rigour into this arena given lack of background

Solution?:

Quite simply -

No. of ways to choose the $2$ days $={18 \choose 2}=:a$

No. of ways to allocate $4$ exams to fill the $2$ days = $6 \cdot 5 \cdot 4 \cdot 3=:b$

No. of ways to allocate the last $2$ exams$=32 \cdot 30=: c$ (2 residual slots on different days)

No. of arrangements of $6$ exams in $36$ slots $=36!/30!=:D$

This gives the answer $p=\frac{a \cdot b \cdot c}{D} \approx 3.77\%$ for the stated configuration.

Not trusting this simple 'guess' heuristic, I coded a simulation to test and the results agree for different parameters (slots/days/target full days/exams), which gives me some confidence, but would be grateful if someone could let me know if they agree/disagree. In particular am interested in whether the 3 different types of calculation (combination vs order-sensitive exam allocation vs residual slot calc) occurring in the numerator are valid - they seem intuitively reasonable to me however if pinned down to prove why, I think would struggle initially to come up with a rigorous argument / set of principles that obtain here.

Separately - as mentioned combinatorics is a bit of a blind spot, just bought myself Cameron's book to up my game, but if anyone has good recommendations for problem books (with solutions), even if recreational (as the above is), would be grateful. Thanks!

Answer 1

If it were'n about exams but about some alternate poker game, we should ask ourselves this :

We have a 36 deck of 18 values and two colors, AM and PM.

A two-pair hand has a 2+2+1+1 configuration. What is the chance to get this hand ?

There are $ {18 \choose 2 } * {16 \choose 2} * 2 *2 \ $ good "hands" among $ {36 \choose 6}$ ; two pairs is a rare hand.

$ P(2+2+1+1) = {73440 \over 1947792} = {90 \over 2387} \approx 3.77\%$

Answer 2

The species formula for one day is,

$Day(X) = \mathit 2(X) + sX.X + d\mathit 2(X)$

meaning that there are three cases : two empty slots, one allocated-one empty, or two allocated slots. Here s is a counter for single-exam days and d is a counter for double-exam days.

The session is the product of the 18 days.

$ Session(X_1, X_2, X_3...) = Day(X_1)·Day(X_2)\cdots Day(X_{18})$

The egf of the first day is

$e.g.f. = \frac {x_1^2} 2 + s.x_1.x_1+ d \frac {x_1^2} 2 = (1+2s+d) \frac {x_1^2} 2 $

The egf of the session is

$e.g.f. = (1+2s+d)^{18} \frac {x_1^2} 2 \frac {x_2^2} 2 ... \frac {x_{18}^2} 2 $

The coefficient of $d^2s^2$ is $good = 73440$ ;

To reveal the number of exams, one day is

$Day(X) = \mathit 2X + tX.X + t^2\mathit 2X$ with egf

$ e.g.f. = (1+2t+t^2) \frac {x^2} 2$

where $t$ counts the number of exams of the day. For entire session,

$e.g.f. = (1+2t+t^2)^{18} \frac {x_1^2} 2 \frac {x_2^2} 2 ... \frac {x_{18}^2} 2 $

The coefficient of $t^6 $ is $all = 1947792$

The required probability is $\frac {good}{all} = 0.0377$