Problem #DES-3

Descriptions
 10–14

Problem

Today we will be solving problems using the Pigeonhole Principle. What is it? Simply put, suppose we are asked to put pigeons inside pigeonholes, but we have more pigeons that pigeonholes. No matter how we try to do it, there will be a pigeonhole with at least two pigeons. For example, consider the following picture, where we have \(10\) pigeons but only \(9\) pigeonholes:

image

No matter how hard we try to arrange the pigeons, it will be impossible to fit at most \(1\) pigeon in each pigeonhole! Here is a way to see why: suppose that in each pigeonhole there was at most \(1\) pigeon. Since we have \(9\) pigeonholes, this means we have at most \(1\times 9=9\) pigeons in total, but this is can’t be true, because we started with \(10\) pigeons!
By pigeonhole we can mean any container, and by pigeon we can mean any object that we want to place inside the containers. This is a simple but very powerful idea, and today we will learn how to use it to solve some difficult problems! Let’s start by seeing a simple example. Can you see what the pigeonholes and the pigeons should be?