Intereting Posts

Which quadrant is the “first quadrant”?
Where does one use holomorphicity in the proof of Goursat's theorem?
Coordinate-free proof of $\operatorname{Tr}(AB)=\operatorname{Tr}(BA)$?
Property of $\dfrac{\sum a_i}{\sum b_i}$ when $\dfrac{a_i}{b_i}$ is increasing
Closed subset of compact set is compact
Convergence of a decreasing sequence and its limit.
Example of set which contains itself
What is a formal polynomial?
How unique (on non-unique) are U and V in Singular Value Decomposition (SVD)?
Method for determining irreducibles and factorising in $\mathbb Z$
The number of subsets of a set of cardinality $n$
How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?
Blowing up a singular point on a curve reduces its singular multiplicity by at least one
compact and locally Hausdorff, but not locally compact
How to show that ${2},\sqrt{3}):\mathbb{Q}]=9$?

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.

- The Hexagonal Property of Pascal's Triangle
- Amazing integrals and how is solved it
- How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?
- Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially
- why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$
- The marriage problem with the constraint that a particular boy has to find a wife.
- A game with two dice
- Proving Crapo's Lemma
- Count the number of possible solutions
- Showing ${n + a - 1 \choose a - 1} = \sum_{k = 0}^{\left\lfloor n/2 \right\rfloor} {a \choose n-2k}{k+a-1 \choose a-1}$

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

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

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.

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.

- How to prove that the uniform topology is different from both the product and the box topology?
- Does anyone know a good hyperbolic geometry software program?
- Upper/lower bound on covariance two dependent random random variables.
- Divisibility for 7
- Help find hard integrals that evaluate to $59$?
- How to find $\lim_{n \rightarrow +\infty } \left(\sqrt{\prod_{i=1}^{m}(n+{a}_{i})}-n\right)$?
- Looking for a (nonlinear) map from $n$-dimensional cube to an $n$-dimensional simplex
- Every principal $G$-bundle over a surface is trivial if $G$ is compact and simply connected: reference?
- Introductory book for homotopical algebra
- Unitary operator is identity
- Analogue of the Schwartz–Zippel lemma for subspaces
- Calculus question about the existence of antiderivative
- A set is closed if and only if it contains all its limit points.
- Cluster Point in Fréchet-Urysohn Space is Limit Point?
- The compact-open topology on the Pontryagin dual is the weakest topology that make all Fourier transforms continuous