# 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.

1,587 questions
Filter by
Sorted by
Tagged with
99 views

### Proofs with the "Purified Pigeonhole Principle". [closed]

In his EWD980 and EWD1094, Dijkstra provides a formulation of the Pigeonhole Principle as such: "For a non-empty, finite bag of numbers, the maximum value is at least the average (and the ...
46 views

### Show that in an equilateral triangle of side 1, among the 10 points inside it there are 2 points whose distance is $\leq \frac{1}{3}$

This should be shown by the pigeonhole principle. In the 10 points, the 3 vertices are included. I guess I need to split the triangle in some way. I tried dividing the triangle in several ways, but I ...
• 537
1 vote
27 views

### Prove that in an 8-element subset of $\{1,2, \dots 15 \}$ there must exist three 2-element subsets whose difference is the same number [duplicate]

I managed to prove that there must exist 2 pairs (pairs here is 2-element subsets) whose difference is the same. Here is my reasoning: We have 14 total unique differences ${1, 2, \dots 14}$ so there ...
• 537
1 vote
77 views

### Prove that in 8 different numbers less equal than $15$ there are at least $3$ pairs of numbers that have the same difference.

Im trying to prove this using pigeon hole principle, if there are $8$ numbers then there are $28$ possible difference values (the diff between the first and each of the remaining $7$ numbers and then ...
• 169
140 views

### Pigeon Hole Principle Proof

Prove using PHP that in any arrangement of the numbers $1,2,\ldots,20$ exist a sequence of $4$ numbers with sum of at least $42$. I know there are $17$ different ...
48 views

### Counterfeit Coins II (green book)

There are 5 bags with 100 coins in each bag. A coin can weigh 9g, 10g, or 11g. Each bag contains coins of equal weight, but we do not know what type of coin each bag contains. You have a digital scale ...
70 views

### Prove that at least two people shake hands the same number of times

There are $n$ people in a party. Any of them can shake hands with any other, any number of times. We need to prove (or disprove) that at least $2$ people do equal number of handshakes. Note that any ...
45 views

### Hamiltonian Paths and Cycles in Graphs

Can someone verify if my proof is correct and rigorous? Thank you in advance! Proposition: Let $G$ be a graph with at least 3 nodes such that every node has at least $n/2$ neighbors. If $G$ has a ...
1 vote
186 views

### Pigeonhole Principle question in a Discrete Geometry Problem

Let $P_1,\dots, P_m$ be polygons contained in the unit square such that $$\sum_{i=1}^m \mathrm{area}(P_i) > n$$ I want to use the pigeonhole principle to argue that there exists a point in the ...
• 377
1 vote
44 views

### What is the maximum number of (non-overlapping) small squares that fit inside a larger square? And similar question for cubes.

I am having a hard time answering the following questions, despite them seeming elementary at first glance. Is it true that the maximum number of (non-overlapping) squares with side lengths $x$ cm ...
• 20.7k
1 vote
110 views

### It might be a pigeon hole but I’m not sure

There is a group of people and in the group, $55.5 \%$ are males. (Correct to first decimal place) Find the minimum number of the male. For example, $111/200=55.5 \%$ $\qquad \qquad$ But how to make ...
1 vote
50 views

### Combinatorics Pigeon Hole Poker Game

Suppose I shuffle a standard 52 card deck deck and give you 25 cards at random from it. You are then tasked with making 5 poker hands from these cards such that each card is in exactly one hand. The ...
• 352
71 views

### The Roman army has 2018 units guarding their provinces. Prove that after 64 days, there were no more provinces with at least 64 units.

Problem: The Roman army has 2018 units guarding their provinces. The Emperor was worried that when there are at least 64 units in a province, they might get together and overthrow the Emperor. So on ...
• 293
1 vote
67 views

### For bijections $f:\mathbb{N}\to\mathbb{Z},$ does $\ \exists\$ infinitely many $N', N$ with $N'>N,\$ s.t. $\vert f(N') - f(N)\vert \geq N(N'-N)?$

Let $f:\mathbb{N}\to\mathbb{Z}$ be a bijection. Proposition $1$: For any $m>0,\ \exists\$ infinitely many $N', N$ with $N'>N,\$ such that $f(N') - f(N) \geq m(N'-N).$ Proof: Eventually there ...
• 20.7k
43 views

### What is the minimum number of pennies that needs to be chosen from a collection so that the restriction is met?

"Discrete mathematics with applications" by Susanna S. Epp contains the following problem: A penny collection contains twelve 1967 pennies, seven 1968 pennies, and eleven 1971 pennies. If ...
160 views

### Pigeonhole Principle Question: Place 1600 points inside a unit square such that there is at least one point inside every rectangle of area 1/200

Tim wants to place $1600$ points inside a unit square such that there is at least one point inside every rectangle of area $\frac{1}{200}$ and with sides parallel to those of the square. Is it ...
• 293
247 views

### A box contains 10 blue, 20 red, 8 green, 15 yellow and 25 white balls. How many balls must we choose to guarantee having 12 balls of the same colour? [closed]

This is a question from the pigeonhole principle. I tried to do it and I got 52 as the answer. But the answer given in my class' notes is 56. I would like to know the correct answer to this question. ...
• 19
83 views

### Monochromatic Triangles with Lattice Centroids in $\mathbb{Z}^2$

There is this problem proving that every $2$-colouring of the lattice points of $\mathbb R^m$ has a collection of $n$ monochromatic points whose centroid is a lattice point of the same colour and I ...
1 vote
17 views

### Pigeon hole principle for pair of numbers that are multiples [duplicate]

I was doing this question and the was curious if my method is valid or if I missed anything out. The question: say we have a subset $X \subseteq \{1, \dots, 2n\}$ where $|X| = n + 1$, show that there ...
33 views

### Proving a conclusion from pigeonhole principle

I learned about the (simple version) of the pigenhole principle, i.e. For n>k, if one distributes n pigeons among k pigenholes, then at least one pigenhole contains two pigens. To write it more ...
• 609
1 vote
196 views

### Approximating $\sqrt2$ by rationals using the Pigeonhole principle

Problem: For any positive integer $m$, I'd like to show that there exist integers $a,b$ satisfying $|a|\leq m$, $|b|\leq m$ and $0< a+b\sqrt{2}\leq \frac{1+\sqrt{2}}{m+2}\,$. Solution attempt: ...
• 119
164 views

### 1000 balls and 100 boxes

There are $1000$ balls labelled $000,001,...,999$ and $100$ boxes labelled $00,01,...,99$. A ball is allowed to put in a box if the number of the box could be obtained by removing one digit from the ...
• 357
56 views

### $A\subset\mathbb{N},$ natural density $1/2.$ Half the members of $A$ are even, half are odd. Is $A$ an (eventual) additive basis of $\mathbb{N}?$

Proposition: If $A\subset\mathbb{N},\ A$ has natural density $d> \frac{1}{2},$ then $\exists\ N\in\mathbb{N}\$ such that $\ n>N \implies \exists\ a,b\in A\$ such that $\ a+b=n.$ Proof sketch: ...
• 20.7k
132 views

### Is there a permutation $\sigma(n)$ of $\{0,1,2,\ldots,m-1\},$ such that $\{(n+\sigma(n))\pmod m:0\leq n\leq m-1\}=\{0,1,2,\ldots m-1\}?$

Given $m\in\mathbb{N},$ is there a permutation $\sigma(n)$ of $\{0,1,2,\ldots,m-1\},$ such that $\{ (n+\sigma(n))\pmod m: 0\leq n \leq m-1 \} = \{0,1,2,\ldots m-1\},\ ?$ Based on computation with ...
• 20.7k
102 views

• 20.7k
308 views

### Proving Pigeonhole Principle is Unsatisfiable

Consider the resolution rule, that is, I can add a resolvent of any two clauses to the formula. My question is: From using only this above rule how to show that the pigeon-hole formula for 3 pigeons ...
48 views

• 207
222 views

### Proving the existence of integers $a, b, c$ such that $\left\lvert a + b\sqrt{2} + c\sqrt{3}\right\rvert < 10^{-5}$ [duplicate]

Prove that there exist integers $a, b, c$ such that $|a|, |b|, |c| \leq 1000$ where not all of them are zero and $\left\lvert a + b\sqrt{2} + c\sqrt{3}\right\rvert < 10^{-5}$ I am stuck on this ...
• 1,858
1 vote
253 views

### What is a better bound on Ramsey numbers?

We have: $$R(\underbrace{3,\ldots,3}_{n\ 3's})=m\implies R(\underbrace{3,\ldots,3}_{n+1\ 3's})\leq(n+1)m-n+1$$ And: $$R(l,l)=m\implies R(l+1,l+1)\geq m+\left\lceil\frac{m-l}{l-1}\right\rceil$$ Can we ...
159 views

### A very complicated icebreaking game

9 strangers play an ice-breaking game at a party for several rounds. For each round, they will sit around a round table and introduce themselves to their neighbors. The rule is that no one is seated ...
62 views

• 369
### BOUNTY Picking $| ad-bc | < \frac{bd}{n-1}$ from $2n$ positive numbers....
Question We consider the set $A_n=\{a_1,a_2,...,a_{2n}\}$ where its elements are different real numbers and strictly positive. Show that for any natural number $n\geq2$ we can choose $4$ different ...