Skip to main content
1 of 4
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is $e^{-1} n - O(1)$; equivalently, the expected size of $\text{im}(f)$ is $(1 - e^{-1}) n + O(1)$.

The second question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer.

Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741