Roommate Pigeons
It makes me really happy whenever I discover a fact in mathematics which has incredible depth even though it looks really simple and obvious in the begining. One of these facts is called pigeonhole principle. It is also known as Dirichlet’s box.
Dirichlet’s Box: German mathematician Lejeune Dirichlet first mentioned his pigeonhole principle in 1834. According to him if more than n objects are placed into n boxes, there will be at least one box that has more than one object.
Raising pigeons is a common tradition in most cities of Turkey. Mardin is one of the leading ones of those cities. Tumbler pigeons of Mardin are really famous.
Let’s say you met a guy who raises tumbler pigeons. He is so enthusiastic about his pigeons; he even built little houses for them. However, you counted the numbers of pigeons and little pigeon houses and you realized that there are more pigeons than pigeon houses. In this case you’ve come to the conclusion that at least one of the houses must have at least two pigeons. In other words, there are pigeons who are roommates.
For instance if you have 10 pigeon houses and 11 pigeons, whenever you put pigeons into their houses, one pigeon will always be left outside. And that pigeon will have to be a roommate to one of those 10 pigeons.
It doesn’t matter what kind of order is being used. In the end there will be a pigeon who will have to share his/her house with another pigeon.
This is the pigeonhole principle.
Game
Are you in a crowded room now? If not, go to a Starbucks and drink a coffee on me. Yes, you can send me the bill. We need crowd for this game.
Look around now: There are at least 2 people who know the same number of person in that room/place.
Rules
- There must be more than 2 people in the room.
- Knowing someone is mutual. If Sean Connery is in the next table, unless he knows who you are too, you can’t count him as someone you know.
- A person should know himself/herself. But, you should do it in your private time. In this game, you can’t count yourself as a person you know.
Example: A group of 5.
In such group, one person can know at most 4 people. (Everyone except him/herself) Also one person can know at least 0 (zero) person. Then we can conclude that in this group of 5, everyone can get to know either one of 0, 1, 2, 3, 4 number of person.
Although in this group if someone knows 0 (zero) number of person, then there can’t be such person who knows 4 people in the same group.
This is why these 5 people can know 0, 1, 2, 3 or 1, 2, 3, 4 numbers of person. We can’t have 0 and 4 at the same group.
Thus, we should assign either one of these 4 numbers to 5 people. Can you see the pigeons?
a. 1, 2, 3, 4
First four people will get 1, 2, 3 and 4 respectively (It doesn’t have to be respectively though. You can use any order you’d like.). Fifth person is left without a number and must be assigned to either one of 1, 2, 3 or 4. No matter which number that person takes, there will be two people that know same number of person.
b. 0, 1, 2, 3
First four people will get 0, 1, 2 and 3 respectively. Fifth person is left without a number and will get either one of those four numbers. Hence there will be two people that have the same number.
One wonders…
Imagine a 5×5 chess board. Every square of the board has a chocolate placed on it. Every chocolate can only be put to an adjacent square on the board. (Two squares are adjacent if they share an edge.)
Chocolates can move to other squares as shown in the photos.
Assume that we moved every chocolate on the board. In the end, will there be exactly one chocolate in every square?
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 