Pigeonhole Principle Problems

Here are some problems relating to the pigeonhole principle to try. Answers are on the pigeonhole principle problems answers page. The first few questions aren't too difficult (if you've read the page on the pigeonhole principle), but the last few may require some thought to find the correct approach.

1. Five numbers are selected at random. Show that, of these five numbers, there exists three of them that sum to a multiple of three.
2. Five points are placed at random inside or on the edge of a unit square. Show that at least two points will be a distance of no more than 1⁄√2 away from one another.
3. Suppose that each square of a 3-by-7 chessboard is coloured either black or white. Prove that in any such colouring, the board must contain a rectangle at least two squares long by at least two squares wide, whose distinct corner squares are all the same colour.
4. Let A be any set of 20 distinct integers chosen from the arithmetic progression 1, 4, 7, ..., 100. Prove that there must be two distinct integers in A whose sum is 104.
5. Show that if there are n guests at a party, then two of them know the same number of guests.
6. Let X be any real number. Prove that among the numbers X, 2X, ..., (n − 1)X there is one that differs from an integer by at most 1⁄n.
7. Prove that in any group of six people there are either three mutual acquaintances or three mutual strangers.
8. Given a set of n + 1 integers between 1 and 2n, show that at least one member of the set must divide another member of the set.