Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then one at least one container has more than one item.

learn more… | top users | synonyms

3
votes
1answer
88 views

Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+ $. Prove that there exists a positive integer $n $ such that $k|n$ and the only digits in $n$ are 0's and 3's
3
votes
4answers
147 views

Let $S=\{3,4,5,6,7,8,9,10,11,12\}$. Suppose 6 integers are chosen from S. Must there be 2 integers whose sum is 15?

How can I go about solving this Pigeonhole Principle problem? So I think the possible numbers would be: $[3+12], [4+11], [5+10], [6+9], [7+8]$ I am trying to put this in words...
3
votes
2answers
201 views

Why is the Ramsey`s theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramsey`s theorem is a generalization of the Pigeonhole principle source But does not say why this is true. I am doing a presentation about the Ramsey theory and also ...
3
votes
3answers
183 views

How would you prove this theory of computation problem?

I have trouble proving the following statement, I'm supposed to do it for our theory of computation course but since I've been trying for days I'm looking for a hint : What is the smallest value ...
3
votes
2answers
397 views

For any arrangment of numbers 1 to 10 in a circle, there will always exist a pair of 3 adjacent numbers in the circle that sum up to 17 or more

I set out to solve the following question using the pigeonhole principle Regardless of how one arranges numbers $1$ to $10$ in a circle, there will always exist a pair of three adjacent numbers in ...
3
votes
2answers
98 views

Pigeonhole Principle and Geometry

Consider any five points in the plane that have integer coordinates: -Prove that there are two points such that the midpoint of the line segment joining those two points also has integer coordinates
3
votes
2answers
86 views

pigeonhole principle problem 3

Prove: For every group of 1009 positive integers, there exist 2 integers of that group, that their sum or difference divide with 2014 without residue. where do I start?
3
votes
2answers
494 views

Pigeonhole Principle: birthdays on same day of week

How many people must be in a room so that at least 10 have a birthday on a Friday? edit: Assume that no two people share the same birthday I'm somewhat confused and see two different ways to ...
3
votes
2answers
169 views

Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
3
votes
3answers
348 views

Pigeonhole principle exercises

I have an exam in combinatorics on Friday and the pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions on this material? Thank you ...
3
votes
1answer
148 views

Lower bound for the number of coin weightings

The book that I am currently studying has the following exercise. Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by ...
3
votes
2answers
182 views

How are the pigeonholes calculated in this pigeon-hole problem?

The question is as follows: To prepare for a marathon, an elite runner runs at least once a day over the next 44 days, for a total of 70 runs in all. Show that there's a period of consecutive ...
3
votes
1answer
94 views

Combinatorics problem; counting in two ways, china 1993

I'm trying to solve the combinatorics problems provided in Yufei Zhao's blog. Can you help me with this one? China (1993): A group of $10$ people went to a bookstore. It is known that ...
3
votes
4answers
191 views

Application of Pigeon-Hole Principle to balls in bins.

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.
3
votes
2answers
76 views

Prove:that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014

Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$). I think the "pigeonholes" here ...
3
votes
3answers
595 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
3
votes
2answers
233 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
3
votes
1answer
74 views

Prove, that in the subset of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums.

Prove, that in the subset with cardinality $25$ of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums. Well, there are at most $150+149=299$ possibilities of sums. But if we have a ...
3
votes
2answers
136 views

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 ...
3
votes
1answer
118 views

Generalizations of the pigeonhole principle

Let us place the numbers $1,2,3....,10$ in a random order on a circular table with 10 places. The question is: prove that there are three consecutive numbers with a sum of 17 or more. I know that we ...
3
votes
3answers
181 views

Proof using pigeonhole and greatest integer (floor) function.

The question is to prove that if m is a positive integer then, $$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right] $$ for $x \in ...
3
votes
2answers
59 views

simple proof for principle of pigeons

I must prove the principle of pigeons but the proofs I find in the internet are too complex. Here's what I can use: Definition $$I_n = \{p\in \mathbb{N}; p\le n\}$$ The principle of the pigeons ...
3
votes
1answer
89 views

Tricky pigeonhole principle question

Say someone is given at least one marble every day for 7 weeks. However, there are never more than 11 marbles given to the person in one week. Prove that there is some period of consecutive days in ...
3
votes
1answer
73 views

What is the minimum of shirts that must be selected to ensure five shirts of the same color are selected?-Pigeonhole Principle

A closet has 3 red, 7 blue and 10 black shirts. What is the minimum number of shirts you’ve to blindfoldedly pick to ensure a. at least 4 of the same color? b. at least 5 of the same color? Soln: I ...
3
votes
2answers
61 views

Prove that if $|S| \ge 2^{n−1} + 1$, then $S$ contains two elements which are disjoint from each other.

I'm trying to use the pigeonhole principle to prove that if $S$ is a subset of the power set of the first $n$ positive integers, and if $S$ has at least $2^{n-1}+1$ elements, then $S$ must ...
3
votes
2answers
83 views

Is my argument correct to solve this textbook problem?

The problem is from M.Bona's "A Walk through Combinatorics", Ch1 Prob 13: There are infinitely many pieces of paper in a basket, and there is a positive integer written on each of them. We know ...
3
votes
1answer
89 views

Pigeon Hole Principle : For $n + 1$ numbers

My question is : Take $n + 1$ numbers out of $1, 2,..., 2n$ Show that there will be two consecutive numbers My Approach : Using the Pigeon Hole Principle , the $n$ holes are ...
3
votes
1answer
95 views

Pigeonhole principle and room full of flies

Room is cube-shaped, with side lengths $3$ meters. $136$ flies flies are in it. Prove that: At any moment you can encompass $6$ flies with a sphere of radius $90$ centimeters. This is ...
3
votes
1answer
334 views

Probability problem- Are there atleast 3 balls with same colour radius and in same box?

The question is as follows, it came in RMO in 1990. It most likely involves probability..as far I think. Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, ...
3
votes
1answer
100 views

Pigeonhole Proof

Let $n_1,n_2,\ldots,n_t$ be positive integers. Show that if $n_1+n_2+\cdots+n_t-t+1$ objects are placed into $t$ boxes, then for some $i$, $i = 1,2,\ldots,t$, the $i$th box contatins at least $n_i$ ...
3
votes
1answer
142 views

A game involving points in the integer plane - who wins?

I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of ...
3
votes
1answer
57 views

An upper bound on the sum of the lengths of chords

Problem: Several chords are drawn in a circle of radius $1$, and each diameter of the circle intersects no more than four of them. Prove that the sum of their lengths does not exceed 13. I couldn't ...
3
votes
2answers
82 views

Three differences $a_{i}-a_{j}$ are the same

Here is the complete question: ** Consider $2n$ distinct positive numbers (with $n>2$) such that each of them is less than or equal to $n^{2}$. Prove that three differences $a_{i}-a_{j}$ are the ...
3
votes
2answers
103 views

Show that given seven real numbers, it is always possible take two of them, such that $\left\vert\frac{a-b}{1+ab}\right\vert<\frac{1}{\sqrt{3}}$

Show that given seven real numbers, it is always possible take two of them, such that $$\left\vert\frac{a-b}{1+ab}\right\vert<\frac{1}{\sqrt{3}}$$ The "Pigeonhole principle" states that if $n$ ...
3
votes
1answer
48 views

Integer Lattice Points

Let $(n_1,m_1),(n_2,m_2),. . .,(n_9,m_9)$ be integer lattice points in the plane (ie. $n_i$ and $m_i$ are integers). Show that the midpoint of the line joining some pair of points is also an integer ...
3
votes
1answer
158 views

Proof that only a certain amount of points can fit in a rectangle

Prove that no more than 8 points can fit in a rectangle with sides d and 2d if any 2 points have to be at least d units away from each other. I have proved that no more than 6 points can fit ...
3
votes
2answers
147 views

Chessboard Pigeonhole Question

"Each square of a 4-by-19 chessboard is colored either green, yellow or red. Prove that the board must contain a rectangle consisting of at least four squares, and such that its four corner squares ...
3
votes
1answer
674 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
3
votes
1answer
91 views

Qn on Pigeon-Hole Principle

Let S be a set of 10 positive integers ≤ 50. Show that there two different (but not necessarily disjoint) subsets of four integers such that the sums of the 4 integers in the sets are equal. Having ...
3
votes
1answer
158 views

Pigeonhole principle problem involving circle and its chords

Several chords are drawn in a circle of radius 1 such that each diameter intersects no more than 4 of them. Prove that the sum of their lengths does not exceed 13.
3
votes
1answer
86 views

Prove that for positive number, some multiple only has 0 and d as it's digits

Let $ n$ be a positive integer, and let $1<=d<=9$. Show that some multiple of $n$ has $0$ and $d$ as its only digits. I don't know how to even start this question. It's under the pigeonhole ...
3
votes
2answers
237 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
3
votes
1answer
74 views

Prove that there exists a numbered socket such that for every orientation, two equal numbers coincide

There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter ...
3
votes
1answer
63 views

Smallest subset of $\{1,2,…,4n\}$ with a certain property

Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$. Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
3
votes
1answer
40 views

7 points on a closed disk, one must be the center

I am trying a pigeonhole strategy for proving this assertion of a MO test: "Given 7 points on a closed disk of radius 1 such that the distance between any two of this points is at least one, then one ...
3
votes
1answer
141 views

Pigeonhole proof of Rational Approximation Theorem

I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states: Show that for any irrational $x \in ...
3
votes
0answers
24 views
+50

Application of Jacobi's Theorem in Box Principle

Today I was going through Problem Solving Strategies by Arthur Engel, and found this in the chapter Box Principle Before the question it says it "treats a theorem of Jacobi and its applications" ...
3
votes
0answers
31 views

Show that if you paint 6 dots on the unit square, then there is always a couple of 2 points with distance <=2/3 [duplicate]

This question is difficult for me. Anyone knows how to divide the unit square by using pigeonhole principle?
3
votes
0answers
36 views

Markov's Inequality and the Pigeonhole Principle

I heard someone in my department claim that Markov's inequality was just a continuous version of the pigeonhole principle. It seemed reasonable, but I'm struggling to make their connection precise. ...
3
votes
1answer
137 views

Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or ...