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
4answers
541 views

How to draw Square Diagonal? [duplicate]

Draw a 5x5 square. In 16 of 25 squares draw diagonals in such a way that no diagonal ends touch. How can I do this?
0
votes
1answer
48 views

Prove existence of 5 non-attacking rooks

Problem: There are $41$ rooks on a $10\times10$ chessboard. Prove that there must exist $5$ rooks, none of which attack each other. I could only observe that at least one of rows and at least one ...
4
votes
1answer
100 views

Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
1
vote
1answer
100 views

Pigeonhole principle for proof

Prove that if a is a natural number, then there exists two unequal natural numbers k and l for which $$ a^k - a^l $$ is divisible by 10. I'm strangely lost on this one. I understand the pigeonhole ...
1
vote
3answers
63 views

Two out of five in a group have the same number of friends…

I recently came across a problem- Prove that in a group of five people,there are two who must have the same number of friends in the group. I assume it must be solved by Pigeon Hole Principle (...
9
votes
2answers
57 views

show that there are at least $\frac{n(n-1)}{2}$elements in this sets

Let $x_{i},i=1,2,\cdots,n$ be real numbers,and such $$|x_{i}-x_{j}|>1(\forall i\neq j)$$ define set $A=\{x_{i}x_{j}+x_{k}|1\le i,j,k\le n\}$,show that $$|A|\ge\dfrac{n(n-1)}{2}$$ How can I go ...
0
votes
1answer
101 views

Lower bound for $R(3, 3,\ldots, 3)$

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges ...
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 ...
1
vote
0answers
47 views

Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
0
votes
1answer
55 views

Tricky probability question which cant be solved using exclusion?

I am confused on how to go about solving this problem- " What is the probability that 2 people in the group have a birthday in the same month out of a)exactly 20 people? b)atleast 20 people" I ...
1
vote
1answer
69 views
2
votes
2answers
79 views

Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2. In my attempt. I try $n=2$, and so ...
0
votes
2answers
30 views

Pigeon hole subset problem

For a given N numbers labeled from 1-N, we need to pick M numbers such that there are atleast K pairs of numbers(x,y) which statisfy x+y=N+1? can anyone help me out with this... please?
2
votes
1answer
133 views

Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

$n$ is also given to be an even number. So I want to prove this by using the pigeon-hole principle. I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as ...
1
vote
2answers
73 views

How to apply Pigeonhole principle in this question

There are 10 people at a party and each person knows an even number of people at the party. Prove that there are 3 people who know the same number of people. Here we assume that knowing someone is ...
1
vote
1answer
64 views

Variation on the “Number of non-bald people in NYC” problem

I have two questions about the following problem, taken from Challenging Problems in Algebra by Posamentier and Salkind: (1) Why is the answer not 1 person? (2) The answer given, without solution, is ...
3
votes
4answers
168 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...
0
votes
2answers
328 views

In a group of 30 people, must at least 3 have been born in the same month? Why?

This is a pigeon hole principle problem and I'm not sure how I can word this to prove that at least 3 have been born in the same month out of 30 people?
0
votes
1answer
86 views

Show that there are at least 2 computers in the network … (Pigeonhole Principle)

A computer network consists of 6 computers. Each computer is directly connected to at least one of the other computers. Show that there are at least 2 computers in the network that are directly ...
4
votes
3answers
286 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
39 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
124 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 week....
0
votes
1answer
88 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
38 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
56 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
144 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
29 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 ...
-6
votes
2answers
92 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
202 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
168 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 in ...
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
139 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
68 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
751 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 the ...
0
votes
2answers
81 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
71 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
266 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
32 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: $d(...
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
213 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
175 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 ...
2
votes
1answer
118 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
135 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
165 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
133 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 am ...
4
votes
4answers
124 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 so ...