# Pigeonhole Principle

Explain the following using Pigeonhole Principle is it is true:

1) If we choose 10 points in a $3 x 3$ inch square, there must be two points of the 10 which are at distance less than or equal to $sqrt(2)$ from each other.

2) Any collection of 12 possible integers must contain two numbers whose difference is divisible by 10.

3) In a $2 x 2$ foot square we select 17 points. Explain why two of these points must be at a distance less than or equal to $sqrt(2)/2$ from each other.

4) Choose 20 points in a $4 x 4$ inch square. Argue that two of these points must be at a distance less than equal to $sqrt(2)$ inches from each other.

5) A square with side length 4 is divided into 16 smaller squares of side length 1 in the obvious way. 19 points are chosen in the interior of the large square. Explain why two of them must have distance less than equal to $sqrt(2)$ from each other.

Im just learning Pigeonhole Principle and came upon these questions. But as simple as they seem, I must not understand PH principle because I don't know how to answer them. As you can tell, most of these questions are quite alike so you don't need to show how to do all of them. But few with detailed explanation would be appreciated so I can get the "feel" for it.

## 2 Answers

Questions (1), (3), (4), and (5) are essentially the same question with different numbers. In (1), for instance, divide the $3\times 3$ square into $9$ one-inch squares. Since you have $10$ points and only $9$ one-inch squares, there must be some square that contains at least two of the points. But the furthest apart two points in a square can be is at opposite ends of a diagonal, and the diagonal of a one-inch square is $\sqrt{1^2+1^2}=\sqrt2$ inches long (by the Pythagorean theorem). Thus, two of the $10$ points must be no further apart than $\sqrt2$ inches. (5) is almost identical, with $3$ replaced by $4$. (4) is the same as (5) with more points than you actually need: as (5) shows, $17$ points would be enough to let you draw the same conclusion. And in (3) you again have to divide the square into $16$ smaller squares, which means making the smaller squares half a foot on each side.

For (2), let the twelve numbers be $a_1,\dots,a_{12}$, and consider the $11$ differences $a_1-a_2,a_1-a_3$, $a_1-a_4,\dots,a_1-a_{12}$. If one of those differences is divisible by $10$, you’re done. Otherwise, two of them must leave the same remainder when divided by $10$. (Why? How many different remainders are there?) Suppose that $a_1-a_i$ and $a_1-a_k$ leave the same remainder when divided by $10$; what can you say about $a_i-a_k$?

Another application of the PHP to #2: two numbers will have a difference divisible by $10$ if and only if the two numbers each have the same units digit. There are only $10$ possible units digits, and you need units digits for $12$ numbers, so...

Slight worry: is zero divisible by $10$?