Problems

Today we will be solving problems using the pigeonhole principle. What is it? Simply put, we are asked to place pigeons in pigeonholes, but the number of pigeons is larger than the number of pigeonholes. No matter how we try to do that, at least one pigeonhole will have to contain at least 2 pigeons. By “pigeonholes" we can mean any containers and by “pigeons" we mean any items which are placed in these containers. This is a simple observation, but it is helpful in solving some very difficult problems. Some of these problems might seem obvious or intuitively true. Pigeonhole principle is a useful way of formalising things that seem intuitive but can be difficult to describe mathematically.

There is also a more general version of the pigeonhole principle, where the number of pigeons is more than \(k\) times larger than the number of pigeonholes. Then, by the same logic, there will be one pigeonhole containing \(k+1\) pigeons or more.

A formal way to prove the pigeonhole principle is by contradiction - imagine what would happen if each pigeonhole contained only one pigeon. Well, the total number of pigeons could not be larger than the number of pigeonholes! What if each pigeonhole had \(k\) pigeons or fewer? The total number of pigeons could be \(k\) times larger than the number of pigeonholes, but not greater than that.

There are 8 students in an online chess club. Show that some two of them were born on the same day of the week.

Ramesh has an infinite number of red, blue and green socks in his drawer. How many socks does he need to pick from the drawer at random to guarantee he will have at least one pair of socks of one colour?

There are \(6\) people playing a game online together. Among any \(3\) people at least \(2\) people know each other. Show that there is a group of \(3\) people that all know each other.

On a certain planet the time zones can only differ by a multiple of \(1\) hour and their day is divided into hours in the same way Earth’s day is divided into hours. Show that if we pick \(25\) cities on that planet, some two cities will have the same local time.

A bag contains balls of two different colours: black and white. What is the smallest number of balls that needs to be taken out of the bag blindly so that among them there are obviously two balls of the same colour?

Tom wants to see a movie with his girlfriend Katie. Unfortunately the ticket selling service is broken. When you buy a ticket, you receive a ticket to a random movie that is being played that day. There are \(7\) movies being played on Friday. How many random tickets does Tom need to buy to guarantee that he and Katie will be able to see a movie together?

In the classroom there are \(38\) people. Prove that among them there are four who were born in the same month.

Is it possible to split \(44\) balls into \(9\) piles so that the number of balls in different piles is different? (Each pile has to have at least one ball)

\(20\) birds fly into a photographer’s studio: \(8\) starlings, \(7\) wagtails and \(5\) woodpeckers. Each time the photographer presses the shutter to take a photograph, one of the birds flies away and does not come back. How many photographs can the photographer take to be sure that at the end there will be at least \(5\) birds of one species and at least \(3\) of another species remaining in the studio?