Nederlands: Deze week weer enkel in het Engels.

にほんごで: こんしゅはなしはにほんごですこしむずかしから。にほんごでありません。

English: The past few weeks there have been many mentions of the pigeon hole principle at work. First, for fun, I put it in my science dialogue slides. Then one of the Belgian guest mentioned it, after that it got mentioned several times in the workshop.

We start with the simple question on what happens if you put ten pigeons into 9 holes:

(image borrowed from wikipedia)

In general, if you have more objects than holes, at least one of the holes will contain at least two of the objects. Exercise for the reader: how many pigeons do you need to guarantee (however you put them into the holes) that one of m holes contains at least n pigeons? Funny consequence: in Tokyo there are at least two people who have precisely the same number of hairs (even if you exclude the bald people).

The pigeon hole principle is also a stepping stone to another interesting principle: Ramsey’s theorem.

(image borrowed from wikipedia)

If, for six dots, you connect each pair of dots with either a red or a blue line then at least three of the dots will be connected by lines of the same colour. The image above shows that five dots are not enough. The fact that you can do this for any number of dots (though the total number of dots needed is somewhat larger than 6) is known as Ramsey’s theorem. Funny consequence: if you have a party of six persons then three of them will either all be friends or all not be friends.

By the way, for four dots all connected by the same colour you would need 18 dots, for five the number which is required is not known. I find it truly delightful that such a concretely stated question already turns out to be extremely hard to answer.