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,536
questions
9
votes
1
answer
238
views
Proving $n$ subsets $A_1, ..., A_n$ of size $\geq 2$ must pairwise intersect.
Let $A_1, ..., A_n \subseteq [n]$ be $n$ subsets of $[n]$ with $|A_i|\geq 2$. Suppose further that for every $B \subseteq [n], |B|=2$, that there exists a unique $i$ with $B\subseteq A_i$. Prove that $...
- 2,212
2
votes
1
answer
92
views
+100
Do large sets have this specific type of self-similarity?
Suppose $(a_n)_{n\in\mathbb{N}}$ is a strictly increasing sequence of
positive integers such that $\displaystyle\sum_{n\in\mathbb{N}}
\frac{1}{a_n}$ diverges, i.e. $(a_n)_{n\in\mathbb{N}}$ is "...
- 17.8k
2
votes
1
answer
43
views
Proof by double counting
Two hundred students participated in a math contest. The had six problems to solve. Each problem was correctly solved by at least 120 participants. Prove, using double counting, that there must be two ...
- 29
4
votes
1
answer
52
views
Basic combinatorics problem on arrangements with a story to it.
First, lets give a short story about the problem which will follow:
I was at school here in Greece. We have school 5 days of the week. 2 random days we have 7 hours of lessons and the rest 6 hours of ...
0
votes
0
answers
97
views
Graph Theory / combinatorics question
Here a problem from Graph Theory I can not solve. There are $2023$ viewpoints on an island. We know that each viewpoint has line of sight to at least $42$ other viewpoints. You should note that, if a ...
- 9
0
votes
1
answer
54
views
Pigeonhole Principle for "n people each in exactly p out of q committees" type of problem
Question: Suppose there're 100 people in 15 committees of 20 people each, and that each person is on exactly 3 committees. Show that there exist 2 committees with overlap >= 3.
I know there's a ...
1
vote
0
answers
53
views
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 ...
- 113
0
votes
1
answer
45
views
Pigeon-Hole Principle Problem: Several Visitors to a Mathematics Library
The problem, from the 'pigeon-hole principle' section of Bona's combinatorics book:
"One afternoon, a mathematics library had several visitors. A librarian noticed that it was impossible to find ...
- 519
2
votes
1
answer
84
views
For every large set $A\subset \mathbb{N},$ there is a concave subsequence of $A$ of length $k$ for every $k\in\mathbb{N}$.
Proposition: Suppose $A\subset \mathbb{N}$ is a large set in the sense
that
$$ \sum_{n\in A} \frac{1}{n} = \infty.$$
Then there exists $a_1 < a_2 < \ldots < a_k,\ $ (not necessarily
...
- 17.8k
2
votes
1
answer
177
views
Has this weak version of Erdős Conjecture on arithmetic progressions been proven, or is it still an open problem?
This question is motivated by Erdős conjecture on arithmetic progressions. It is a weaker version of Erdős Conjecture, but I do not know how to prove it.
Erdős conjecture on arithmetic progressions ...
- 17.8k
1
vote
1
answer
53
views
what is the use of pigeon-hole principle in proving $\inf_{n,m \in \mathbb{N}}|n-2m\pi|=0$?
The resource of the proof is : http://mypage.concordia.ca/mathstat/pgora/m364/Density.pdf
The proof used the pigeon-hole principle for infinite cases which was strange.
The proof is:
Denote by $<x&...
- 1,001
1
vote
2
answers
70
views
Can you partition the set of 9 consecutive integers 1 to 9 in 2 sets, s.t. no member of either set is the mean of two other members of the same set? [duplicate]
Is it possible to partition the set $\Omega=\{1,2,3,4,5,6,7,8,9\}$ in two subsets $\Omega=A\cup B$, $A\cap B=\emptyset$, such that no member of either subset is the mean of two other members of the ...
- 11.2k
0
votes
0
answers
22
views
If $\sum_{i=1}^t(n_i-1)+1$ pigeons are distributed among $t$ pigeonholes, then there exists a pigeonhole that contains at least $n_i$ pigeons.
Full exercise description
$Proof$.
Suppose that for each $i$ the pigeonhole $h_i$ contains at most $n_i-1$ pigeons. Then the total number of pigeons at most is $(n_1-1)+(n_2-1)+\cdots+(n_t-1)=\sum_{i=...
1
vote
0
answers
55
views
PHP - 6 x 16 checkerboard painted in 3 colors
I have a suggestion for a solution to a question and I would appreciate if you could verfy it.
Question
Consider a $6\times 16$ checkerboard painted in 3 colors (let's say $0,1,2$ ).
Prove that there ...
- 631
4
votes
1
answer
109
views
How could I have known to use the pigeonhole principle to solve this problem?
I was tyring to solve:
Let $a_1,a_2,\dots ,a_{2n}$ and $b_1,b_2,\dots ,b_{2n}$ be two sequences of integers such that for every $1\leq i \leq 2n$: $1\leq a_i , b_i \leq n$.
Prove there exists two ...
- 631
1
vote
0
answers
56
views
Minimum number of attendees in a party
At a party, you realise that everyone, except you, has shaken
hands with exactly three other people; you have shaken hands
with only one other person. Determine the minimum number of
attendees at this ...
- 45
1
vote
0
answers
71
views
Pigeonhole Principle application for number of hair
As a beginner, I was reading Pigeonhole Principle from Wikipedia. The statement of PHP as it stated was very clear to me.
The pigeonhole principle states that if n items are put into m containers, ...
2
votes
1
answer
85
views
Every set of size $2^n-1$ has a subset of size $2^{n-1}$ that sums to a multiple of $n$
Is the following statement true? If so, how can it be proved?
Every set of $2^n-1$ positive integers, $n\in\{1,2,\dots\}$, has a subset of size $2^{n-1}$ that sums to a multiple of $n$.
An attempt ...
- 11.2k
0
votes
1
answer
66
views
Prove that any sequence $a_1,...a_n$, $n \geq 5$ contains a subsequence whose elements properly added or subtracted give a multiple of $n^2$
As in the title:
Prove that any sequence $a_1,...a_n$, $n \geq 5$ contains a subsequence whose elements properly added or subtracted give a multiple of $n^2$
The idea is probably to use the pigeon ...
- 759
0
votes
0
answers
39
views
Proof of Dilworth's theorem using PHP
I'm trying to prove "Dilworth's theorem" using Pigeonhole principle.
Definitions
Let $ (X,\le)$ be a partially ordered set, it means:
$\forall x \in X: x\le x$
$\forall x ,y\in X: x\le y,y\...
- 631
4
votes
1
answer
43
views
Combinatorics Pigeonhole Problem find Max Number of Possible Different Colors such that each Sub-Group of Size 9 from 60 Contains 3 Same-Color Balls
Let a box contain 60 colored balls. In each group of 9 balls, at least 3 of them are the same color.
What is the maximal number of possible colors which will allow the above condition to be true?
I ...
- 43
1
vote
1
answer
138
views
How many players are needed so that two evenly matched teams can be picked?
We have a pool of $n$ players of a game, each player is assigned a "skill" which is an integer $1\leq s\leq 10$. We are now going to pick teams of $2$ players, where the team's skill is ...
- 3,072
0
votes
1
answer
70
views
Simple friendship proof
I'd like to know if this is a valid proof. It is the friendship Friendship Puzzle, and i understand that while this question exists,i still want to know if my method is valid
The theorem is that:
At ...
3
votes
1
answer
59
views
If $A\subset \mathbb{N}$ with $\vert A \vert = \infty,$ does $\exists p\in\mathbb{P}_{\geq 3}$ such that $\vert\{a\pmod p:a\in A\}\vert=p$ or $p-1?$
Let $\mathbb{P}$ be the set of prime numbers.
My original question was going to be this:
If $A\subset \mathbb{N}$ with $\ \vert A \vert = \infty,\ $ does $\ \exists\ p\in\mathbb{P} $ such
that $\ \...
- 17.8k
0
votes
0
answers
40
views
Clarification over the proof of Caretheodory's theorem
I am reading this note online and I am having trouble understanding the proof of theorem 20, Caretheodory's theorem. The author writes
"...Since $\int_0^2 \frac{dr}{r}$ diverges near $r=0$, we ...
- 3,237
1
vote
1
answer
73
views
Pigeonhole principle: Waitress trying to match food orders by turning the round table [closed]
In a restaurant, a group of 16 friends takes seat on a table. The table is round, rotatable has 16 chairs placed around it symmetrically so one can easily rotate it and change meal position. 9 of the ...
- 31
2
votes
1
answer
75
views
sum of 2 subseries is equal [duplicate]
We have two sequences of $2n$ numbers $a_1, a_2,\dots, a_{2n}$ and $b_1,\dots . b_{2n}$, $1\leq a_i , b_i \leq n.$
Prove that there exist 2 sub-sequences, 1 from each sequence, such that the sum of ...
- 53
1
vote
1
answer
49
views
Confusion in Generalization of Pigeonhole Principle
I want to ask if this two statements are correct:
If N objects are placed into k boxes, then there is at least one box containing at most ⌈N/k⌉ objects. (originally the statement is "at least&...
- 59
0
votes
1
answer
64
views
movie in a table [duplicate]
10 Chinese and 10 Japanese people are sitting in a round table that can rotate both sides.
On the table, there are 20 personal screens with a movie on them, 10 movies in Chinese and 10 in Japanese.
...
- 53
5
votes
0
answers
41
views
Buss' Polynomial-Size Frege Proof of the Propositional Pigeonhole Principle
S. Buss described a polynomial-size Frege proof of the propositional pigeonhole principle in the paper Polynomial size proofs of the propositional pigeonhole principle (the definition of the Frege ...
- 185
6
votes
1
answer
171
views
Given two unbounded subsets $X,Y$ of $\mathbb{R},$ do there exist three points of $X$ whose translation and stretch approximates three points of $Y?$
Suppose $X$ and $Y$ each are subsets of $\mathbb{R}$ that are bounded below and unbounded above (and therefore infinite).
Given $\varepsilon>0,\ $ do there exist $\ x_1,\ x_2,\ x_3 \in X;\ x_1 < ...
- 17.8k
1
vote
2
answers
118
views
Proof by pigeon hole principle.
I've been practicing discrete math recently and I'm stuck on this problem. Could someone help me with this, give me some hint or direction? I figured it was the pigeonhole principle, but I can't ...
- 133
4
votes
1
answer
207
views
Choose n+1 numbers from 1 to 2n. Prove that among the chosen numbers, there is always a pair of different numbers (a,b) such that a|b or b|a [duplicate]
My reasoning so far is:
If the number 1 is chosen, we are done since 1 divides any number.
If 2 is chosen, then the remaining n numbers to choose will either be all odd (including 1) or contain an ...
- 186
2
votes
0
answers
76
views
51 points are inside a unit square. How do I prove that a circle with radius 1/7 can always cover 3 of them without using the Pigeonhole Principle?
I looked at this page: 51 points lie inside an square of side 1.Prove that it's possible to draw a circle of radius $\frac17$ covering at least 3 of theses points
Instead of using the Pigeonhole ...
- 302
4
votes
1
answer
169
views
Bats in a number of Caves (THE BAT CAVES!!!)
This problem is kind of like a combinatorics type of problem, I believe.
But also has the feeling that it kind of makes use of the so-called "pigeonhole principle".
I recall doing a problem ...
- 831
1
vote
1
answer
79
views
Pigeonhole on sums of subsets from {1,…,99}
Good evening fellow curious minds
Suppose S is a subset of size 10 from the positive integers 1,…,99.
Is it true that there will always be two distinct pairs from S that have the same sum?
I think a ...
- 445
7
votes
2
answers
254
views
Given increasing sequence of numbers, what is guaranteed min length the longest subseq. s.t. differences of terms are either decreasing or increasing?
It would be better if I could fit "differences of consecutive terms" in the title, but I ran out of space. Anyway, here is a more precise version of my question:
Given $n,$ for any given ...
- 17.8k
1
vote
2
answers
75
views
If we remove $\lfloor (2^n-2)/3 \rfloor$ from a set of $\{1,\dots,2^n\}$, there is still a pair of integers $a, b$ such that $a=2b$
To count the maximum number of integers from $1\dots 2^n$ s.t. none of them is twice the other we can group them by their biggest odd divisor, i.e. represent each $m$ as $m=2^k (2c+1)$, so we can take ...
- 763
8
votes
1
answer
521
views
How to prove that, among any 𝑛+1 distinct odd integers from {1,…,3𝑛}, at least one will divide another?
This was one of the exercises in my textbook and I've been working on it for well over 10 hours over the span of 3 days without much progress. I don't think that it's even supposed to be a hard ...
- 628
6
votes
1
answer
105
views
Given $p - 1$ integers not divisible by an odd prime $p$, we can change signs of some (all or none) of them so that their sum is divisible by $p$.
I'm currently trying to solve this problems, but ran out of ideas. In my textbook this problem goes after a series of problems related to variations of this zero-sum problem, but it may or may not be ...
- 763
1
vote
1
answer
57
views
paint a board with two colors without repeating the amount painted in each row rows
A child is playing coloring his chessboard and will paint each square either completely blue or completely red. To give it a personalized touch, he wants to paint the same number of red squares as ...
1
vote
0
answers
36
views
Fomin et al., Mathematical Circles Chapter 4- Pigeon Hole Principle Problem 12. Max. no. of kings that can be placed so no two put each other in check
I found this problem in Mathematical Circles in the Pigeon Hole Principle chapter:
What is the largest number of kings which can be placed on a chessboard so that no two of them put each other in ...
- 2,429
6
votes
1
answer
87
views
Pigeonhole principle, a sum question
$$\text{Let }\space S\subset\{1,2,\ldots,101\}\text{ s.t }\space|S|=52.\\\text{Prove that there exist different values }a,b,c\in S\text{ s.t }\\a+b=c.$$
That question appeared at my last Discrete math ...
- 865
0
votes
1
answer
60
views
At a party of only 2 people, will these 2 people actually know each other? - Pigeonhole Principle
I am aware of the proof - Given that there are $n$ people in a party $\left(~\mbox{where}\ n \geq 2~\right)$, there are $2$ people who know the same number of people.
Assuming:
knowledge is mutual so ...
- 55
0
votes
1
answer
51
views
PigeonHole proof - 8 Points Circle Radius 1
I am asked to proof the following :
Using the pigeonhole principle, prove that among any 8 points on a circle of radius 1, there are at least two points whose distance is less than 1.
Just by using a ...
- 1
-1
votes
2
answers
47
views
Minimal Exam Versions Required so no student is adjacent to the same version
An interesting problem as we approach final exams in some places of the world.
Suppose a classroom has the desks arranged in a 5x4 array. There are 18 students. What is the minimal number of exam ...
- 777
14
votes
1
answer
272
views
Least eccentricity vertex can't have the most average distance
The eccentricity of a vertex $\epsilon (v) $ is the maximum of distances $d(v, u) $ over all other vertices $u$. The average distance of a vertex avgd$(v) $ is the average of all $d(v, u)$, more ...
- 408
4
votes
1
answer
110
views
If $A\subset\mathbb{N}$ has positive upper density, $B\subset\mathbb{N}$ is infinite, does $\exists c$ such that $\vert\{c+a:a\in A\}\cap B\vert>k?$
Definition: A subset A of the natural numbers is said to have positive upper density if $\ \displaystyle\limsup _{n\to \infty }\frac{\lvert A\cap \{1,2,3,\dotsc ,n\}\rvert}{n}>0.$
Let $\ A\subset \...
- 17.8k
2
votes
1
answer
75
views
Winning strategy in a pigeonhole principle related game
Let us have the following game. The player $F$ claims that the usual pigeonhole principle is not true and, moreover, they have a counterexample, i.e. a function which maps $n + 1$ pigeons injectively ...
1
vote
0
answers
29
views
Pigeonhole coloring bound
I am stuck on this problem from a combinatorics book. I tried applying the pigeonhole principle to show that there are at least n/r numbers with the same color, and applied the formula for (x choose 2)...
