# Questions tagged [pigeonhole-principle]

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

890 questions
52 views

34 views

### prove something must happen with pigeonhole principle [duplicate]

I'm given the following problem: In every group of 15 cars , there are 3 that were manufactured in the same country. prove that in a group of 100 cars there are 15 cars that were manufactured in ...
87 views

### Examples of the Pigeonhole Principle

As most of you might know, the Pigeonhole Principle basically states that If $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item It ...
66 views

48 views

### Prove that amongst 10 sticks of length 1 to 55 there are 3 that form a triangle

I'm trying to prove, that amongst 10 sticks, which length can vary from 1cm to 55cm, there are 3 (or at least 3), using which one can form a triangle. I feel like I should use Dirichlet's pigeon ...
66 views

### Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show that there is a blue triangle or a red tetrahedron

Could I get any help with this one, I'm lost. We know that the Ramsey number $R(3, 3)$ equals $6$. Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show ...
91 views

### Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$.

Problem : Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$. I am not getting any ideas in solving this problem. So, there ...
24 views

### Pigeonhole principle about finding a specific group of four people

A bridge club has $10$ members. Every day, four members of the club get together and play one game of bridge. Prove that after two years, there is some particular set of four members that has played ...
79 views

### 19 arrows hit the target in the form of a regular hexagon page length of 1 m. Show that at least two arrows are less than 60 cm away.

Problem: 19 arrows hit the target in the form of a regular hexagon page length of 1 m. Show that at least two arrows are less than 60 cm away. My attempt: Idea is to use Pigeonhole principle to ...
45 views

### 105 integers contains a subsequence with sum divisible by 99.

I recently came across a problem which states that $$\\$$ Given any sequence of 105 integers there will always be a subsequence of consecutive elements in the sequence, whose sum is divisible ...
73 views

### Pigeonhole Principle with Sets…consider the set X= { 1, 2, 3, 4,5}… [closed]

I need help with a combo problem. I'm not sure what this is asking and how to begin. Consider the set $X=\{1,2,3,4,5\}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the ...
500 views

### A woman selects balls from a bowl at random …

A bowl contains 10 red balls, 10 blue balls and 10 black balls. A woman selects balls at random without looking at them: a) How many balls must she select to be sure of having at least three ...
47 views

152 views

### Combinatorics: Prove that $x, y, z$ exist such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$

Suppose we have a subset of $2n-1$ numbers from the set ${1, 2, 3, ..., 2^n-2}$. Prove that there exits $x, y, z$ such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$ I'm fairly new to this topic, ...
72 views

### Bob selects four points on a $10\times 10$ square.

Bob selects four points on a $10\times 10$ square. Is it true that two of them are less than $\sqrt{101}$ units apart? I know how to prove things like this for five points. These seems ...
35 views

### how to use the pigeon hole principle on a graph problem? [duplicate]

I have this given problem: In a class there is 6 students,every 2 students of 6 know each other in advance or they don't. Show that there is 3 students that don't know each other in advance or that ...