Skip to main content

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.

Filter by
Sorted by
Tagged with
-1 votes
1 answer
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 ...
iceyspinglass's user avatar
0 votes
1 answer
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 ...
powerline's user avatar
  • 537
1 vote
0 answers
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 ...
powerline's user avatar
  • 537
1 vote
1 answer
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 ...
user1188938's user avatar
0 votes
1 answer
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 ...
Student0_0's user avatar
0 votes
1 answer
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 ...
Connor Brown's user avatar
2 votes
1 answer
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 ...
ztart14578's user avatar
4 votes
1 answer
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 ...
cheesepizza's user avatar
1 vote
2 answers
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 ...
JazzGuitar7's user avatar
1 vote
0 answers
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 ...
Adam Rubinson's user avatar
1 vote
0 answers
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 ...
science krowemoh's user avatar
1 vote
0 answers
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 ...
Evan Semet's user avatar
3 votes
1 answer
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 ...
Jacob Phan's user avatar
1 vote
0 answers
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 ...
Adam Rubinson's user avatar
0 votes
1 answer
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 ...
Vlad Mikheenko's user avatar
4 votes
2 answers
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 ...
Jacob Phan's user avatar
-1 votes
1 answer
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. ...
User's user avatar
  • 19
2 votes
1 answer
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 ...
math.enthusiast9's user avatar
1 vote
0 answers
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 ...
user438409385's user avatar
0 votes
1 answer
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 ...
NTc5's user avatar
  • 609
1 vote
2 answers
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: ...
Arthr's user avatar
  • 119
5 votes
1 answer
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 ...
Yadis Beles's user avatar
3 votes
1 answer
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: ...
Adam Rubinson's user avatar
3 votes
1 answer
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 ...
Adam Rubinson's user avatar
2 votes
2 answers
102 views

Problem understanding pigeonhole principle

In the café, 4 people are having lunch, whose names are $v_1$, $v_2$, $v_3$, and $v_4$. Some of them know each other. The number of acquaintances of person $v_i$ (who are in the café) is denoted by $d(...
gujaral's user avatar
  • 353
1 vote
0 answers
40 views

Proving that the Set of Outputs of a Function f(n) over Natural Numbers Has a Power of 2

I have a function f(n) defined over the set of natural numbers, where each input n corresponds to a unique output f(n), ensuring that the function's values are distinct. I am trying to prove that the ...
KKboi's user avatar
  • 21
1 vote
2 answers
92 views

$2n$ knights around a table with namecards, is it possible that for every rotation there is exactly one person with a correct namecard?

I need help with the following puzzle: Consider a round table which hosts $2n$ knights. At each seat, there is a namecard of one knight. The knights don't necessarily sit in front of their own ...
Steve's user avatar
  • 184
1 vote
2 answers
102 views

Question on counting the number of triangles formed by 1999 points in a square

I was reading an explanation for a solution to an Olympiad problem as follows: Let $S$ be a square with the side length 20 and let $M$ be the set of points formed with the vertices of $S$ and another ...
deadskull16's user avatar
2 votes
1 answer
78 views

Is there a Hamiltonian cycle of $m$ x $n$ rectangular lattice points (these are the vertices) in $\mathbb{R}^2$ such that no two edges are parallel?

Let $m,n\geq 2$ and consider the rectangular lattice of $mn$ vertices in $\mathbb{R}^2,\ (i,j);\ i\in \{1,2,\ldots,m\},\ j\in \{1,2,\ldots,n\}.\ $ Call these vertices $X_1, X_2, \ldots, X_{mn}.$ Is ...
Adam Rubinson's user avatar
1 vote
3 answers
78 views

How many different ways are there to choose of $n$ subsets $\{i,j\},$ each of length $2,$ from $[2n]:= \{1,2,3,\ldots, 2n \}$?

How many different ways are there to choose of $n$ subsets $\{i,j\},$ each of length $2,$ from $[2n]:= \{1,2,3,\ldots, 2n \}$ ? So for example for $n=25,\{ \{1,2\}, \{3,4\}, \{5,6\}, \ldots, \{49,50\} ...
Adam Rubinson's user avatar
0 votes
2 answers
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 ...
user avatar
0 votes
0 answers
48 views

Suppose $n\in\mathbb{N}.$ Partition $\{1,2,3,\ldots,2n\}$ into $n$ pairs. Is it true that the maximum pair product is $\geq n^2 ?\ $ Or $\geq n(n+1)?$

Suppose $n\in\mathbb{N}.$ Partition $S_n:=\{1,2,3,\ldots,2n\}$ into $n$ pairs. Is it true that the maximum pair product is $\geq n^2 ?\ $ Or $\geq n(n+1)?$ So for example for $n=3$, we have: $S_3:=\{1,...
Adam Rubinson's user avatar
4 votes
1 answer
133 views

A question on pigeonhole principle? [closed]

I came across the following question which I could solve using a "trial-and-error" approach. However, is there a systematic way of solving it using the pigeonhole principle? "When ...
q9801's user avatar
  • 49
0 votes
0 answers
92 views

Number of subsequences of consecutive sequences in a non-periodic sequence

Let $a_1, a_2, \ldots$ be a sequence which is not eventually periodic, i.e. there do not exist constants $K$ and $N$ such that $a_m = a_{m+K}$ for all $m \geq N$. Prove that the number of distinct ...
DesmondMiles's user avatar
  • 2,853
-2 votes
1 answer
83 views

Pigeonhole principle: Show that out of 7 lines in a plane we can choose 3 paralel lines or 4 concurrent lines. [closed]

There are $7$ lines in a plane. Show that we can always pick either $3$ paralel lines or $4$ concurrent lines. Show that it won't work for $6$ lines. I have no idea where to start with this.
runtotherescue's user avatar
-2 votes
1 answer
151 views

if we choose 14 different numbers from the following set 1, 2, 3, 4,...,20, then ... [closed]

Using the pigeonhole principle, prove that if we choose 14 different numbers from the following set {1, 2, 3, 4,...,20}, then definitely there are two numbers such as a and b (among our 14 selected ...
Jenny's user avatar
  • 7
1 vote
1 answer
98 views

prove the existence of the same classes [closed]

I am a beginner in combinatorial mathematics, this is a combinatorial mathematics course assignment. With 31 students each taking at least 6 courses from a total of 10 courses, I need to prove the ...
whisperwind's user avatar
8 votes
1 answer
255 views

Two element subset of $\{1,2,\dots,100\}$ with sum of elements being a square

Prove that every 50-element subset of $\{1,2,\dots,100\}$ contains two elements $a,b$ such that $a+b$ is a square of integer. Any 50-element subset of the set $\{1,2,\dots,100\}$ has $\binom{50}{2}=...
user1260135's user avatar
8 votes
2 answers
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 ...
MangoPizza's user avatar
  • 1,858
1 vote
1 answer
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 ...
Roddy MacPhee's user avatar
4 votes
1 answer
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 ...
Gregory Wijono's user avatar
5 votes
1 answer
62 views

Is the sum of minimum distances of a bounded sequence in $\mathbb{R}^d$ convergent?

Let $d\in\mathbb{N};\ $ let $ x_n \in \mathbb{R^d}\ \forall\ n\in\mathbb{N},\ $ with $(x_n)_{n=1}^{\infty}$ bounded. Let $(t_n)_{n=1}^{\infty}$ be the sequence obtained from $\left(\displaystyle\min_{...
Adam Rubinson's user avatar
1 vote
1 answer
140 views

I have a pool of 10 practice exams, which 2 of these will appear on the exam, and I want to see at least one of the ones I completed, on exam day.

How many exams do I need to complete if I have a pool of 10 practice exams to choose from, which 2 of these will appear on the exam, and I want to see at least one of the ones I completed, on exam day....
Mathsider's user avatar
2 votes
1 answer
76 views

Pigeonhole Principle for 2 element subsets of X = {1,2,3,4,5,6 }

"Consider the set $X = \{1,2,3,4,5\}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the 2-element subsets of $X$. Can you put these 10 pigeons into the two holes in a way ...
Ator's user avatar
  • 23
0 votes
1 answer
112 views

Pigeonhole Principle problem on the inequality of the sums of two subsets

Good day, this problem is designed to use the Pigeonhole Principle. For a finite set A of integers, denote by $s(A)$ the sum of numbers in $A$. Let S be a subset of {$1,2,3,...,14, 15$} such that $s(B)...
didenko jack's user avatar
5 votes
2 answers
254 views

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 ...
IONELA BUCIU's user avatar
0 votes
0 answers
17 views

Find the largest $n\in\mathbb{N}, \forall a_1,\cdots, a_7 \in S_n, \exists S,T \subseteq S_7, \sum_{i\in S} a_i = \sum_{j\in T} a_j$

Let $S_n = \{1,2,\cdots, n\}$ for every positive integer n. Find the largest $n\in\mathbb{N}$ so that $\forall a_1,\cdots, a_7 \in S_n, \exists S,T \subseteq S_7, \sum_{i\in S} a_i = \sum_{j\in T} ...
user3472's user avatar
  • 1,225
1 vote
1 answer
76 views

Combinatorial problem based on the Pigeonhole Principle

Good day,i came across this problem from the section on the Dirichlet principle. And I’m completely stumped, I’d be grateful for any idea A point $(a_1;a_2)$ in the x — y plane is called a lattice ...
didenko jack's user avatar
2 votes
3 answers
152 views

If $0<q<2000$, then at most $10$ consecutive terms of the arithmetic progression $a,\; a+q,\; a+2q\dots$ can be primes

Show that if $0<q<2000$, then at most $10$ consecutive terms of the arithmetic progression $$a,\; a+q,\; a+2q\dots$$ can be primes. If not, then there is an $r$ such that $$a+rq,\; a+(r+1)q,\; \...
Sayan Dutta's user avatar
  • 9,592
0 votes
1 answer
118 views

Pigeonhole Principle: Prove that among 12 mutually different 2-digit integers we can always find 2 numbers whose difference is...

The job is to use Pigeonhole Principle and prove that you can choose $12$ different 2-digit integers whose difference will be a 2-digit number with the same ciphers $(11, 22, 33, ..., 99)$. I've ...
runtotherescue's user avatar

1
2 3 4 5
32