# Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if you can send me links\books\or just a lone problem.

I will divide my answer into two parts: resources from internet, and resources from this very site.

## Some resources on the internet

This short paper contains a lot of pigeonhole principle-related problems, both easy and hard ones, and both with and without solution.

This web page contains also a number of pigeonhole problems, from basic to very complex, with all solutions.

Take a look also at these fun applications of the pigeonhole principle

## Some problems from this site

You can find a lot of interesting problems that are solved with pigeonhole principle on this site.

Numbers

101 positive integers placed on a circle

101 positive integers whose sum is 300 are placed on a circle. Prove that it is possible to choose some consecutive numbers from these numbers whose sum is equal to 200.

Choose 100 numbers from 1~200 (one less than 16) - prove one is divisible by another!

Prove that if 100 numbers are chosen from the first 200 natural numbers and include a number less than 16, then one of them is divisible by another.

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that for any 52 integers two can always be found such that the difference of their squares is divisible by 100.

Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Suppose you have a list of n numbers, n≥2. Let A be the set of differences of pairs of these n numbers. Prove or disprove that at least one element of A must be divisible by n−1.

Proving an interesting feature of any $1000$ different numbers chosen from $\{1, 2, \dots,1997\}$

Assume you choose 1000 different numbers from the group {1,2,…,1997}. Prove that within the 1000 chosen numbers, there is a couple which sum is 1998.

People and objects

Discrete Mathematics - Ice Cream random samples

Suppose there are 5 different types of ice cream you like. How many random samples ice cream must be eaten to guarantee that you have had at least 7 samples of one type?

A question related to Pigeonhole Principle

In a room there are 10 people, and none of them is older than 60, and each is at least 1 year old. Prove that one can always find two groups of people (with no common person) such that the sum of ages is the same in both groups.

combinatorics: The pigeonhole principle

Assume that in every group of 9 people, there are 3 in the same height. Prove that in a group of 25 people there are 7 in the same height.

Pigeonhole Principle question

There is a row of 35 chairs. Find the minimum number of chairs that must be occupied such that there is a consecutive set of 4 or more occupied chairs.

Another pigeonhole principle question

A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at least 6 of them must have completed the same electives as each other.

Geometry

Pigeonhole principle for a triangle

Consider a equilateral triangle of total area 1. Suppose 7 points are chosen inside. Show that some 3 points form a triangle of area $\leq\frac 14$.

Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can't arrange 100 points inside a 13×18 rectangle so that the distance between any two points is at least 2.

Pigeon principle question: Nine points in a diamond

A diamond (a parallelogram with equal sides) is given, and its sides are 2 cm long. The sharp angels are 60 degrees. If there are nine points inside the diamond, prove that there must be two of them so that the distance between them is at most 1 cm.

Pigeonhole principle and a decagon

The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that there are 3 consecutive vertices whose sum is at least 14.

Polygon and Pigeon Hole Principle Question

Seven vertices are chosen in each of two congruent regular 16-gons. Prove that these polygons can be placed one atop another in such a way that at least four chosen vertices of one polygon coincide with some of the chosen vertices of the other one.

Smallest number of points on plane that guarantees existence of a small angle

What is the smallest number n, that in any arrangement of n points on the plane, there are three of them making an angle of at most 18∘?

There are many such problems (with solutions!) in the Math.SE archives. You can try other keywords in the search box at the top right of the page to look for more problems.

The famous Proofs from the book contains a chapter on Pigeon-hole and double counting. You can find there several cute applications of the pigeon-hole principle.

This turned up in a routine google search of the phrase "pidgeonhole principle exercise" and appears to be training problems for the New Zealand olympiad team. It contains numerous problems and has some solutions in the back.

• the link is not working anymore, do you have a copy, ot new link location? – VividD Jan 16 '14 at 6:22

IF $\alpha>0$ is irrational, then the fractional parts of $n\alpha$ forms a dense subset of $[0,1]$.

Given a positive integer $n>0$, Fibonacci numbers modulo $n$ is periodic.

These are very famous ones from number theory. There are proofs of these using pigeonhole principle.