Season 6 Episode 3

OOMC Season 6 Episode 3. Crate Labelling Problem

We've got three crates with three labels, but every label is on the wrong crate. In this episode we solve the problem and explore harder variants.

 

Further reading

Principle of Inclusion and Exclusion (PIE)

There’s a Brilliant article with some exercises and another description of the inclusion-exclusion principle if you’d like more.

I thought that this might be a good place to do something slightly different; we can prove the three-set version of PIE by using the two-set version of PIE. First here's the two-set version of PIE;

$$| A \cup B | = |A|+|B|-| A \cap B | $$

Remember that $\cup$ means "or" and $\cap$ means "and". Now we want to find an expression for $|A \cup B \cup C |$. Let’s write that as $|A \cup \left( B \cup C \right) |$. Now use two-set PIE to get

 $$|A \cup \left( B \cup C \right) |= |A|+|B\cup C| -|A \cap \left(B\cup C\right)|$$

Now the right-hand side is already looking good, but we can do better if we note that $A \cap \left(B\cup C\right)=\left(A\cap B\right)\cup\left(A\cap C\right)$. Now use two-set PIE again on this to get

$$| \left(A\cap B\right)\cup\left(A\cap C\right) |=|A\cap B| + |A \cap C| - |(A\cap B)\cap (B \cap C)|$$

If we put this all together and do some tidying-up then we end up with the three-set PIE (details left as an exercise for you!). This is perhaps preferable to the argument we did on the livestream about counting and double-counting and corrections, because it just uses previously-established rules without doing something new and complicated.

 

Crate problems

There are $n$ crates, each with different contents, and each has a label indicating the contents, but all $n$ labels have been mixed up and each has been put on the wrong crate, one label per crate. How many crates do you need to open (in terms of $n$) in order to fix the labels?

 

Double derangements

The paper by Even and Gillis that we briefly looked at on the livestream is available at this link.

It's very advanced in comparison to most of the things that we cover on the livestream – the authors are free to use mathematics from beyond A-level (of course) and they do so without warning.

For something much more readable, see this account of how Joe Gillis solved the derangements problem at this link. I mentioned a bit of this story on the stream, but it’s still worth a revisit.

 

Laguerre Polynomials

One of the things used by Even and Gillis in their paper is a Laguerre Polynomial. This is a sequence of polynomials, and the $n$th polynomial in the sequence is

$$L_n(x)=\frac{e^x}{n!} \frac{d^n}{dx^n} \left( x^n e^{-x} \right)$$

Written like that, I suppose it's not obvious that it's even a polynomial. The notation here indicates that we're supposed to take $n$ derivatives. If you haven't seen the product rule for differentiation yet, then this is not something that you're able to calculate yet, but if you have seen it then try to calculuate $L_1(x)$ and $L_2(x)$. These are solutions to something called the Laguerre differential equation, which is

$$ x y’’+(1-x)y’+ny=0$$

That differential equation turns up in (for example) the quantum-mechanical description of the hydrogen atom, and the structure of this family of polynomials goes some way to explain electron orbitals and thus the shape of the periodic table.

 

Birthday paradox

The birthday "paradox" is the idea that if you have $n$ people whose birthdays each fall on one of $d$ days at random, then the probability that two people have the same birthday can be non-trivial even if $n$ is much less than $d$. In the normal statement of the problem, $d=365$, and if $n>23$ then the probability of a shared birthday is more than $\frac{1}{2}$.

In general, if $d$ is a large number, then the probability of a shared birthday increases with $n$ and does "most of its changing" (from roughly zero to roughly 1) at around about $n\approx\sqrt{2d}$.

This has an application; it means that if you're planning to hand out random ID numbers to people, you need to make the maximum ID number at least as big as the square of the number of people, to avoid the chance that you'll give the same ID number to two people. Or run some sort of centralised system to make sure that you don't re-use ID numbers.

In cryptography, people sometimes want to encrypt a file with a complicated (and in some sense "random") function. The question of whether your function gives different outputs for different inputs (and could therefore be decrypted by the person you’re communicating with) is another version of the birthday problem.

Wikipedia does a pretty good job of describing this problem of "hash collision".

 

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.

Please contact us with feedback and comments about this page. Last updated on 16 May 2023 11:15.