What Is the Pigeonhole Principle?

[Music] the pigeonhole principle is one of those ideas that sounds completely obvious but turns out to be pretty useful here's the idea let's say there are four pigeon holes and let's also say we have five pigeons each of which needs to be put into one of those holes the pigeon hole principle says that after we've put each pigeon into a pigeon hole there must be at least one pigeon hole that has multiple pigeons in it and that's it that's the whole idea or i suppose to state the principle a little more generally if we have n pigeons put into m pigeon holes and n is greater than m then there must be at least one pigeonhole that contains more than one pigeon when i first heard this principle it just sounded obvious and i wondered how an idea so straightforward and trivial could actually prove practical but it turns out a lot of problems have solutions that in whole or in part can be answered by applying the pigeonhole principle of course usually we're not literally talking about pigeons and pigeonholes but instead talking more generally about any objects if we distribute n items across m groups and there are more items than there are groups then at least one of those groups must have more than one item in it solving certain problems then just comes down to identifying what our pigeons and pigeon holes actually are so today let's take a look at some interesting applications of the pigeonhole principle and let's start with a puzzle say we have a chess board an 8x8 grid of alternating light and dark squares if we take dominoes each of which can cover up two of these squares we can lay them out in such a way that they perfectly tile this chessboard that's not too much of a surprise there are 64 squares on the chessboard and here we're using 32 dominoes to cover the whole board perfectly with no dominoes sticking out no square left uncovered and no square covered twice if we remove one square from this chessboard it's pretty clear that it's now impossible to tile the board there's an odd number of squares but using dominoes we could only ever cover an even number of squares but what if we removed two squares from the chessboard from opposite corners of the board is it still possible to tile this board perfectly it might not be so clear at first and you can try it attempting to lay out tiles in just the right places but ultimately you'll find that you won't be able to perfectly tiling this board with dominoes isn't possible but how do we know well to tile 62 squares we would need 31 dominoes and importantly when each domino is laid on the board it's going to cover up two squares one dark square and one light square no matter how that domino is oriented and how many light squares are on this chessboard anyways well a full chess board has 32 light squares but since we removed two light squares from opposite corners of this board we now have 30 light squares see where this is going we can now apply the pigeonhole principle our pigeons are the 31 dominoes and our pigeon holes are the 30 light squares each domino needs to cover one of the light squares and since we have more dominoes than light squares there therefore must ultimately be at least one light square covered by multiple dominants and since in a perfect tiling each square should be covered by exactly one domino we can therefore say that a perfect tiling isn't possible let's take a look at another example let's imagine planet earth which for simplicity we'll here assume is a perfect sphere earth can be divided into a northern hemisphere and a southern hemisphere but that's not the only way to divide the earth into two pieces a hemisphere is just any half of the sphere and a closed hemisphere is a hemisphere that includes the dividing line between the two halves so now here's the question if you pick any five points on earth can you find some closed hemisphere that includes at least four of those five points we can try an example we pick five points at random and try some different hemispheres and in this case we can eventually find a hemisphere that contains four of those five points but will that always be the case it turns out the answer is yes we can start by saying that with any two points on earth we can use those two points as the dividing line between hemispheres after that we're left with three remaining points each of which must belong to one of these two hemispheres do you see where the opportunity for the pigeonhole principle is [Music] if we let the points be our pigeons and the hemispheres be our pigeon holes look what happens we have more points than hemispheres so there must be some hemisphere that has at least two points and if that hemisphere has at least two of these points plus the two points on the dividing line then it therefore contains four out of the five points on earth so for any five places on earth four of them will always be on the same half of the planet proven by the pigeonhole principle and the pigeonhole principle isn't just useful for solving puzzles it has practical computational consequences too one natural extension of the principle has to do with compression converting some longer representation of data to some shorter representation there's a particular form of compression called lossless compression where as the name suggests no information is lost in the compression process in other words once we have the compressed version of the data we can perfectly reconstruct the original information using the pigeonhole principle we can prove that there is no way to have a lossless compression algorithm that always produces a smaller output for any given input how can we do that well if the input has n bits there are two to the n possible values the input can take on and if the compressed output has some smaller number say m bits then there are two to the m possible outputs from this compression algorithm there are more possible inputs than outputs and that's the key for the pigeonhole principle the inputs are our pigeons the outputs are our pigeon holes and since there are more inputs than outputs then there must be some output that is associated with at least two different inputs and if the same output is associated with two different inputs then there's no way to perfectly reconstruct what the input is from this output because we wouldn't know which of these two was actually the original data all of these problems and more different problems that at first glance don't look similar at all ultimately rely on the same principle to solve them and that's the beauty of taking some idea and formalizing it in a generalizable way once you know the principle even if it's obvious you can begin to see pigeons and pigeonholes as they appear in other seemingly unrelated problems and as a result see where the principle might be helpful in solving all sorts of different problems

Channel: Spanning Tree

Views: 2,892,894

Keywords: computer science, pigeonhole, principle, discrete mathematics, proofs, discrete, math, computation, logic, dirichlet

Id: B2A2pGrDG8I

Length: 8min 23sec (503 seconds)

Published: Sun Aug 02 2020