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

4
votes
3answers
246 views

Application of the pigeon hole principle

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows: "During a month with 30 days, a ...
0
votes
0answers
38 views

Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\} $". Here is my proof ...
2
votes
2answers
117 views

Prove using Pigeon Hole principle.

A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, to avoid tiring himself, he decides not to play more than 12 games during any calendar ...
0
votes
1answer
77 views

Proving by pigeonhole principle that a duocolored 3x9 rectangle will always contain subrectangles whose corners are the same color.

Lets say each square of a 3x9 rectangular board is colored either blue or red. How can I prove mathematically that for any such coloring, the board will always contain a subrectangle (paralell to the ...
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. ...
2
votes
1answer
55 views

Are Square and equilateral triangle the only convex regular ngons that can be composed to smaller versions of themselves?

While I was trying to make an analogous question to Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\frac{\sqrt{2}}{n}$ apart, using equilateral ...
6
votes
1answer
141 views

Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\sqrt{2}/n$ apart

I know I need to use the pigeonhole principle to prove this, but I don't know exactly how. What I think I could do is divide the unit square into $n^2$ squares. Using Pythagoras theorem, the maximum ...
0
votes
1answer
28 views

If $x,y,a_1,\ldots,a_n\in\mathbb Z$ and $a_1,\ldots,a_n\in[x,y],$ then $a_1=x,a_2=x+1,\ldots,a_n=y$ (proof verification)

I recently solved a problem in which I used the following fact. If there are exactly $n$ integers in the interval $[x,y]$ ($x,y\in\mathbb Z$) and $a_1,a_2,\ldots,a_n$ are integers of that interval ...
-5
votes
2answers
88 views

Discrete mathematics: Question regarding “Pigeonhole principle”. [closed]

Each point in the plane is coloured either red or blue. Show that there are two points of the same colour which are exactly 1 cm apart.
10
votes
2answers
1k views

Pigeonhole principle: Five points on an orange

Five points are drawn on the surface of an orange. Prove that it is possible to cut the orange in half in such a way that at least four of the points are on the same hemisphere. (Any points lying ...
3
votes
4answers
194 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
1answer
165 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 ...
1
vote
3answers
113 views

Pigeonhole principle 3

I need help on this question, I'm lost and really don't know how to proceed: Use the pigeonhole principle to prove that in a round-robin chess tournament (with 18 participants) there will be at least ...
3
votes
1answer
138 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 ...
1
vote
1answer
51 views

Problem involving weights of blocks and pigeonhole principle

So I have been trying to solve the following problem: Suppose you are given n blocks, each of which weighs an integral number of pounds, but less than n pounds. Suppose also that the total weight of ...
7
votes
2answers
715 views

Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is ...
0
votes
2answers
79 views

problem related to pigeon hole principle

please help me to solve this using pigeon hole principle Suppose that S is a set of n integers. Show that one can choose a nonempty subset T of S such that the sum of all elements of T is divisible ...
-1
votes
1answer
66 views

Discrete matematics, using pigeonhole principle [closed]

Please help me solve this problem: Assuming that in a box there are $10$ black socks and $12$ blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the ...
0
votes
1answer
253 views

Prove that two non-bald residents of NYC have exactly the same number of hairs.

In New York City there are two non-bald people who have the same number of hairs ( the human head can contain up to several hundred thousands with maximum of about 500,000) How can I prove the ...
0
votes
1answer
31 views

Question about use of pigeonhole principle to show that there are at least 3 common neighbors to two vertices

Let $G$ be a simple graph such that $|V|\ge 5$, also $x,y$ are vertices that aren't adjacent. Prove that if $d(x),d(y)\ge \frac {n+1}2$, then $x,y$ has at least $3$ common neighbors. My attempt: ...
1
vote
1answer
83 views

Problem with the application of the pigeonhole principle.

A football team plays at least one match per day in a month of $30$ days , but no more than $45$ matches in that month. Is it true that in some consecutive days in the month, the team will play ...
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
2answers
206 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 ...
0
votes
2answers
158 views

How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects?

Example: How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3? I understand how to do it when we need to make sure that at least ...
1
vote
1answer
115 views

Pigeonhole principle, choosing 1-8 numbers out of 27

prove that for every 8 choosen numbers from 10 to 36 you can always make equalities. number can be used once. examples. let say that the choosen numbers are 10, 11, 12, 15, 18, 25, 32, 36 you can ...
6
votes
1answer
134 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
6
votes
4answers
1k views

Given 5 integers show that you can find two whose sum or difference is divisible by 6.

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" ...
1
vote
2answers
80 views

Pigeonhole question with finding a number.

Show that there is a number consisting only of 1’s that is divisible by 2001. I know that it relates to the Quotient-Remainder Theorem and I got m=2001q+r, r: [0,2001). But I don't know how it ...
4
votes
1answer
164 views

Students knowing others

There are 25 students in the class. It is known that among any three of them, two know each other. Show that there is a person who knows at least 12 other people. Thoughts: I know this is true since ...
1
vote
3answers
131 views

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays each. Miklos Bona rates this question as "less difficult than average" while I am stuck on it although I ...
4
votes
4answers
122 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
2answers
38 views

How to show $x,y,z \in A$ - Functions, Combinatorics

If $A \subseteq \{1,2,3,4,5,6\}$, how to show that for every $A$ there are $x,y,z \in \{1,2,3,4,5,6\}$, where $x,y,z$ can also be the same or at least not different from each other, and the following ...
2
votes
2answers
73 views

Pigeonhole Principle question - sum of natural numbers

Let $f:\{1,2,...,15\} \rightarrow \Bbb N$ be a function such that $\sum_{i=1}^{15} f(i) =100$. $f(15+1)$ is defined to be $f(1)$. I have shown that $14\leq f(i)+f(i+1)$ for some $1\leq i \leq15$ ...
-1
votes
1answer
61 views

Pigeonhole principle, choosing point in a region [closed]

Consider the following region: It is bounded by a regular hexagon whose sides are of length 1 unit. Show that if any 7 points are chosen in this region (hexagon), then 2 of them must be no further ...
2
votes
1answer
133 views

51 Dalmatians grouping

Suppose there are 51 dalmatians and number of dots on each dalmatian is not null. Prove (or dis-prove) there is always a grouping such that at least one group has total number of dots as multiple of ...
4
votes
3answers
84 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
2
votes
1answer
111 views

Prove that if a graph has six vertices, then at least one of G or $\bar{G}$ has a subgraph isomorphic to $K_3$

I think this proof is related to proving to Theorem on friends and strangers which can be proved with the pigeonhole principle. But I am at a loss as to what are the holes and pigeons in this case. I ...
2
votes
1answer
62 views

pigeonhole principle - Oneway Island

There is a group of cities with the follwoing rule: Each city is connected to each city linked by a oneway street: For any two different cities $A$ and $B$ is it you either go directly from $A$ to ...
0
votes
0answers
57 views

Pigeon Hole Principle - proof of d as a positive integer

Let $d$ be a positive integer and consider any set $A$ of $d+1$ positive integers. Show that there exists two different numbers $x, y\ \epsilon\ A$ so that $ x \mod\ d = y \mod\ d$ and $x =/= y$. ...
3
votes
1answer
90 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 ...
2
votes
1answer
65 views

$5$ points on a sphere [duplicate]

Diffuse $5$ points on a sphere. Prove there is a closed half-sphere that has at least $4$ points on it.
0
votes
0answers
79 views

combinatorics - pigeonhole principle - 2

I've advanced a little with this question but I'm not sure that I'm in the right direction. For any set $X$ with $n$ positive numbers, $n>5$, prove the existiance of subset $Y \subset X$ so that ...
12
votes
1answer
3k views

How many people would you need in a room to ensure with 100% probaility that three have the same birthday?

I am vaguely aware of the Pigeonhole principle and I understand that you would need 367 people to ensure that two people have the same birthday. I think that it may be required to have 734 people in a ...
9
votes
2answers
185 views

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^\circ$? It is clear that $n>9$, since the vertices of a ...
2
votes
2answers
104 views

show that at least 3 balls have same weight

You are given 49 balls of colour red, black and white. It is known that, for any 5 balls of the same colour, there exist at least two among them possessing the same weight. The 49 balls are ...
1
vote
1answer
114 views

Show that for any set of 201 positive integers less than 300, there must be two whose quotient is a power of three (with no remainder)

I guess we should not consider the zeroth power of 3 because it is equal to one. Any positive integer is a multiple of 1. Lets define the set S3 of integers that are multiples of 3 strictly less ...
1
vote
2answers
139 views

Pigeonhole principle: In every set of 100 integers, there exist two integers whose difference is a multiple of 37

What are the pigeons and the pigeonholes and how to prove this statements? At first I tried to the following: There are "100 choose 2" or 4950 pairs of integers. But I don't know how to move ...
0
votes
3answers
75 views

Pigionhole Principle

Among any group of 3000 people there are at least 9 who have the same birthday. I cant figure out what's the object is and what's the box. And, how to apply it in the principle
5
votes
1answer
117 views

Problem with $20$ integers less than $70$

20 pairwise distinct integers each less than 70 are taken and their pairwise differences are taken(magnitude of the difference). Show that there always exists 4 equal numbers. I somehow found ...
0
votes
1answer
56 views

Whether it is the pigeonhole principle?

I had a question, and I am just wondering if it is a question that involves combinations/permutations or the pigeonhole principle. In a class are $20$ students. What is the probability that at least ...