Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as too broad by Brian Rushton, Thomas Andrews, mathematics2x2life, Joe Z., Sasha Jan 16 at 3:08

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
This will be very difficult to answer since "hard to very hard" is not well-defined if we don't know more about your background. To start, have a look at these: jan.ucc.nau.edu/~mk84/226/worksheets/pigeonholesol.pdf and math.utah.edu/mathcircle/notes/pigeon.pdf. Are these too easy? Are they suitable? –  M Turgeon Sep 11 '12 at 19:51
    
These aren't so taugh.. –  Tomer Galanti Sep 13 '12 at 7:34
    
    
Duplicate of math.stackexchange.com/q/430116/18398 –  Joel Reyes Noche Jan 16 at 5:16

5 Answers 5

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
the link is not working anymore, do you have a copy, ot new link location? –  VividD Jan 16 at 6:22

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.


Some problems from this site

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

Numbers

A Pigeonhole Principle problem

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.

Of any 52 integers, two can be found whose difference 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.

The pigeonhole principle question

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$.

pigeonhole principle - 100 points in $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.

share|improve this answer
    
+1. That's unbelievably many resources –  Ganesh Jan 16 at 22:25

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.