# 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
Filter by
Sorted by
Tagged with
238 views

1 vote
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 ...
22 views

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 ...
1 vote
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 ...
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 ...
59 views

1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...