Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [pigeonhole-principle]

This tag is for questions involving the Pigeonhole Principle, which roughly states that if $n$ items are placed in $m$ containers and $n>m$, then at least one container has more than one item.

The Pigeonhole Principle roughly states that if $n$ items (e.g. pigeons) are placed in $m$ containers (e.g. pigeonholes) and $n>m,$ then at least one container has more than one item. Stated more formally, the Pigeonhole Principle asserts that there is no injective function whose codomain has smaller cardinality than its domain.

An example application of the Pigeonhole Principle is a demonstration that if five points are placed on a sphere, then there must be some hemisphere which contains at least four of these points: any two points define a great circle, which divides the sphere into two hemispheres. By the Pigeonhole Principle, one of these two hemispheres must contain at least two points. This hemisphere then contains four of the five points (the two on the boundary, and the two found via the Pigeonhole Principle).

1565 questions
3
votes
4 answers

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 \mathbb{R}$. Where $[x] =n$ such that $ n \leq x
AvatarOfChronos
  • 1,701
3
votes
2 answers

Pigeonhole Principle Points in a Triangle

Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible value for the shortest distance between any two…
Andy
  • 31
3
votes
1 answer

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 from a math class, I couldn't devise an appropriate solution,…
VividD
  • 15,966
2
votes
0 answers

2014 points inside a cube

$2014$ points are chosen inside a cube with side $13$. Can a cube with side $1$ be found inside it so that it doesn't contain any of chosen points? This must be a problem solved using pigeonhole principle, however I still can't see a clever…
VividD
  • 15,966
2
votes
2 answers

Show that some 5 consecutive chairs must be occupied.

A group of 25 people are seated in a row of 30 chairs. Show that some 5 consecutive chairs must be occupied.
heyhuehei
  • 683
2
votes
1 answer

pigeonhole principle with sequence of numbers

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$.
roi
  • 21
2
votes
2 answers

Pigeonhole Principle Proof

2004 flies are inside a cube of side 1. Show that some 3 of them are within a sphere of radius 1/11. I am not sure how to begin the proof especially since we are asked to work on a sphere rather than the given cube.
Jebediah
  • 543
2
votes
1 answer

Have we met before?

If there are $6$ people at a party, then either at least $3$ people met each other before the party or at least $3$ people were strangers before the party. Solution from Xinfeng Zhou's A practical Guide to Quantitative Finance: Let's say that you…
Kom
  • 123
2
votes
2 answers

Math olympiad question involving pigeonhole principle

Prove that among any 101 distinct positive integers, there exists 11 numbers with a sum divisible by 11. I have tried to seperate the 101 positive integers into 10 sets such that 1 set has at least 11 integers, but I do not know what to do from…
FAN WENDI HCI
  • 247
2
votes
0 answers

A Question on the Pigeon Hole Principle

Question: Let $S = \{1,2,3,.....,44,45\}$. Find the maximum value of $n$ such that it is possible to select $n$ numbers from $S$ and arrange them in a circle in such a way that the product of any two adjacent numbers in the circle is less than…
Math Noob
  • 49
2
votes
4 answers

If the the sum of $n$ numbers is $10n$, Prove there exist $k$ numbers that their sum is at least $10k$

I am baffling this question for a couple of days now and haven't seen a proof to this yet. So as the title says: We have $n$ numbers such that their sum is $10n$ and we need to prove using dirichlet principle (pigeonhole principle) that there exist…
eladgl
  • 61
  • 6
2
votes
1 answer

Points in the plane - Pigeonhole Principle - Sharpen the result

Thirteen points are given in the plane so that among any three of them there is a pair whose distance is less than $1$. Prove that it is possible to select seven of the points so that they are all interior to a circle of radius $1$. This problem…
user863763
  • 21
2
votes
2 answers

Pigeonhole principle question confusion

Now I understand it. I just learnt this principle. I am doing a problem in which there's a box with many red socks, green socks and blue socks. First question was how many minimum socks should I pick out without looking to be absolutely sure to get…
kuch nahi
  • 6,789
2
votes
1 answer

Prove there is an integer divisible by 2003

I don't quite understand why $s_j$ $-$ $s_j$ is divisible by $2003$ means that there is an element in this sequence that is divisible by $2003$. Aren't they trying to prove for one single element? Not for a difference of the sequence's two…
user634512
2
votes
2 answers

Pigeonhole principle with congruence

Let $S\subset \mathbb{Z}/n\mathbb{Z}$ where $n$ is even and $n\geq2$, and $\mid S\mid\geq n/2$. Show that there exist $x, y\in S$ with $x+y\equiv 0 \pmod{n}$ The hint is the pigeonhole principle and it is my first time heard about it. I read the…
Will
  • 91
1 2 3
…
14 15