Maths is full of cool theorems. The Pigeonhole Principle is one of my favourites because of the fact that it is so powerful and quite tricky to prove, yet so intuitive and easy to understand. Before I can talk about it though, I need to introduce you to the world of mathematical functions.
Functions
In maths, a function is a ‘mapping’ from one ‘space’ to another. The ones that people are used to seeing are things like f(x) = x2 but functions don’t have to involve algebra at all. I find that it’s easiest to explain them using diagrams and by giving real names to things, so here goes…
Have a look at the diagram above. There are 2 spaces or sets, which in this case are the countries England and Australia. England is the domain – the place that we are mapping from, whilst Australia is the co-domain (also called range), and it is the place that we are mapping to. England and Australia both contain cities, which are represented by the nodes within each set.
In this scenario, a function is a set of roads that takes us from somewhere in England to somewhere in Australia. All the English cities must take us somewhere – so a set of roads is a valid function only if each city in England has a road going to some Australian city. The roads are one-way only in our case, so sadly no Aussies can return to the homeland.
There are a few types of road arrangement that have special names:
Injection
An injection or ‘injective function’ is when each element in the co-domain is mapped to by at most one of the elements in the domain. In our example, to have an injection, we are not allowed to have an Australian city that has 2 (or more) roads coming into it from different English cities. We couldn’t have roads from both London and Manchester going to Sydney, for example.
The diagram below shows one possible injective function. Sydney, Canberra and Perth each have one road coming into them from distinct English cities. Melbourne has no roads coming into it, but that’s fine for an injection because nobody really cares about Melbourne anyway…
Surjection
A surjection or ‘surjective function’ is when every element in the co-domain is mapped to. So now we need to show love to all the Australian cities – even Melbourne. Each city in Australia must have a road coming into it to have a surjection. Importantly, they don’t all have to come from unique cities in England. As you can see below, all 3 Australian cities are mapped to, but notice that London has 2 roads coming out of it whilst Sydney has 2 going into it. This wouldn’t be allowed in an injection, but it is okay for a surjection.
Bijection
Finally, if a function is injective and surjective, then it is bijective. In other words, each English city must have one road coming out of it and each Australian city must have one road going into it. Each English city is ‘paired’ with an Australian one.
Notice a key feature of the bijection: you cannot have a bijection when there are different numbers of cities in each country. If you look back at the injection example where we had Canberra as well, there is no way to pair all of the cities together between the two countries.
The Pigeonhole Principle
Here comes the interesting bit. The theorem is named after the pigeonholes in which you put mail, and for good reason. Formally the theorem states that:
“For two sets A and B: if set A contains n elements, set B contains m elements and n>m then there can be no injection from A to B.”
Pretty simple isn’t it? In essence, it says that if England had more cities than Australia, we couldn’t create an injective mapping between them.
Suppose we took our bijection diagram and added poor old Luton Town to England. Remember, the definition of an injection is that each Australian city can only have 1 or 0 roads coming into it. Also, the definition of a function states that every English place must have a road coming out of it. Then we must create a road from Luton going to somewhere in Australia. But wherever we link Luton to, that place will already have a road going into it from somewhere else. Hence, the pigeonhole principle tells us that it is impossible to have an injection in this case.
This is clearly a simple example, but the pigeonhole principle becomes pretty cool when trying to think of more complicated and interesting problems. Suppose you were in a room with 365 other people (making it 366 in total). You can then proceed to wow everyone with your new found mathematical knowledge and say “Ahh, the pigeonhole principle tells me that set A (the room) has 366 elements (people), but set B (the year) only has 365 (days). Therefore, there is no injection from A to B! So at least one of you must have the same birthday as me!”
Perhaps a more subtle example might be: suppose you pick any 12 positive integers. Then you must be able to subtract one of the numbers from another one to get a multiple of 11.
Why? If you have a set of 12 numbers, if you divide the numbers in the set by 11, you must get a remainder of somewhere in between 0 and 10. That’s 11 different remainders that are possible. But there are 12 numbers in the set and so the pigeonhole principle tells you that at least 2 of the numbers have the same remainder after division by 11. If you subtract one from the other, you’ll get a number which is exactly divisible by 11, and hence is a multiple of 11!
Try to work through that example by choosing 12 actual numbers and checking it out if it didn’t make sense the first time. When you do get it, you’ll realise the power of the pigeon!