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
3answers
170 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
371 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
48 views

How does the pigeonhole principle intuitively suggest incorrect computations of probability?

Here is an interesting false computation using the pigeonhole principle. Suppose I am asked to compute the probability that three successive tosses of a fair coin will have the same result. It can ...
3
votes
2answers
67 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
182 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
2answers
453 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
165 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
338 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
147 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
173 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
4answers
166 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
73 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
523 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
224 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
73 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
131 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
117 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
179 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
1answer
63 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
56 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
79 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
87 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
92 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
316 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
98 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
140 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
47 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
2answers
99 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
134 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
135 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
617 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
82 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
84 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
233 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
58 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
146 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
138 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
29 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
1answer
130 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 ...
3
votes
1answer
65 views

let $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b \in A$ such that $n \leq a-b \leq 2n$

I'm having difficulties solving this question and would appreciate a nudge in the right direction. I think this is best solved with pigeonhole, but what are the pigeons and what are the holes?
3
votes
1answer
121 views

Prove that there is an element in $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},…\}$ having fractional part less than 0.01

Given a set $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},...\}$, prove that some of the elements have fractional part less than 0.01 when written in decimal form. Here is my attempt so far: Divide the range ...
3
votes
1answer
115 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
3
votes
0answers
106 views

Milk bottles and pigeonhole. [duplicate]

Possible Duplicate: Chess Master Problem A child drinks at least 1 bottle of milk a day. Given that he has drunk 700 bottles of milk in a year of 365 days, prove that for he has drunk ...
2
votes
7answers
305 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
2
votes
1answer
204 views

geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
2
votes
3answers
212 views

A pigeonhole problem from “Conjecture and Proof”

I don't really know how to start this problem at all. I would like a solution or even hints. "Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$" The chapter in ...
2
votes
3answers
152 views

One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
2
votes
3answers
441 views

Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.

Choose any 38 different natural numbers less than 1000. Prove that among the selected numbers there exists at least two whose difference is at most 26. I think I need to use pigeon hole principle, ...