Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pigeonhole-principle]

Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then at least one container has more than one item.

1
vote
1answer
52 views

Prove that $\forall A_k\subset \{1,2,\dots,3n\}$, with $|A_k|=2n$, $\exists (a_i,a_j)\in A_k$ s.t. $a_i-a_j=n-1$

Let $n\geq2$ be an integer. Prove that every subset $A_k\subset \{1,2,\dots,3n\}$, with $|A_k|=2n$, contains two elements $a_i,\ a_j\ $ s.t. $\ a_i-a_j=n-1$, and prove that $\nexists\ a_i,\ a_j \in ...
2
votes
2answers
52 views

When $n$ is an integer such that $n>1$, $S$ is an arbitrary subset of {$1,2,3,…,3n$} and the number of elements of $S$ is $n+2$, prove that

When $n$ is an integer such that $n>1$, $S$ is an arbitrary subset of {$1,2,3,...,3n$} and the number of elements of $S$ is $n+2$, prove that there exist integers $x, y$ in $S$ such that $n<y-x&...
-1
votes
2answers
34 views

prove something must happen with pigeonhole principle [duplicate]

I'm given the following problem: In every group of 15 cars , there are 3 that were manufactured in the same country. prove that in a group of 100 cars there are 15 cars that were manufactured in ...
5
votes
7answers
87 views

Examples of the Pigeonhole Principle

As most of you might know, the Pigeonhole Principle basically states that If $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item It ...
2
votes
2answers
66 views

Show that there exists $i\in \lbrace 1, 2, 3 \rbrace $ s.t. there exists $a, b\in A_i $ s.t. $a+b\in B $.

Let $A=\lbrace 1, 2, 3,..., 2019\rbrace= A_1\cup A_2\cup A_3$, where $A_1\cap A_2=A_2\cap A_3= A_1\cap A_3=\emptyset $ and $B=\lbrace 672, 1008, 1344, 1680, 2016\rbrace $. Show that there exists $i\...
-2
votes
0answers
28 views

PHP? Induction? [duplicate]

A wrestling tournament is formatted such that every possible pair of the participants compete against each other in a 1v1 match where there is always a winner and a loser. There are a total of $2^n$ ...
0
votes
1answer
42 views

Pigeonhole principle question 1

A competition is formatted such that every possible pair of participants compete against each other in a 1 vs. 1 match where there is always a winner and loser. There are a total of 2^n participants ...
-1
votes
0answers
34 views

Pigeonhole Principle with Sequences and averages [closed]

There are 100 books, each with a distinct length from 101 to 200 words inclusive. I arbitrarily select 21 of them. I then choose 4 of the 21 books and calculate the average length of the 4 books to be ...
1
vote
0answers
43 views

Truth/lie problem using Pigeonhole Principle

In an island, there is only two kinds of inhabitants; knights who always tell the truth and knaves who always lie. You meet 3 inhabitants A, B, and C and have the following conversation with them. ...
0
votes
0answers
36 views

Is there n such that $3^n$ starts with 2019 [duplicate]

Does there exist a natural number n such that $3^n$ starts with the digits 2019 ? How do I solve this question ?
3
votes
2answers
385 views

Is it possible to find 2014 distinct positive integers whose sum is divisible by each of them? [closed]

Is it possible to find 2014 distinct positive integers whose sum is divisible by each of them? I'm not really sure how to even approach this question. Source: Washington's Monthly Math Hour, 2014
0
votes
1answer
59 views

Round table and microphones, a pigeonhole problem

20 people are sitting around a table. 9 of them want to give a speech, and there are 9 microphones on the table in front of 9 random people. The microphones are fixed but we can turn the table.How can ...
2
votes
1answer
80 views

For any eight points on an equilateral triangle of side $1$, there's at least one pair of those points at most $1/3$ apart

Let's say we have an equilateral triangle of side length $1$. Show that for any configuration of eight points on this triangle (on the sides or in the interior), there is at least one pair of from ...
1
vote
0answers
33 views

Proving divisibility by pigeonhole principle

There is a dartboard with labeled numbers 1 through 20. The score obtained by throwing a dart is the number that the dart lands on, so if it lands on 10, the score is 10. If 11 darts are thrown, and ...
-1
votes
2answers
80 views

How many people have their first and last name beginning with the same letter?

In a country, with a population of 11.000.000 people, how many of them have their first and last name beginning with the same letter? (e.g. Alex Abus, Peter Pen etc.) . Consider that their alphabet ...
0
votes
1answer
39 views

Pigeonhole again

There are $10$ bird cages with the maximum of $5$ birds inside it. How many birds should be prepared so that I can be sure that there are $3$ cages with $2$ birds inside it? My answer : I fitted all ...
9
votes
4answers
1k views

$100$ birds in $21$ cages each with $≤ 10$, with least cages having $≥ 4$ birds?

A bird cage could only fit a maximum of $10$ birds. If a house has $21$ bird cage and $100$ birds. A bird cage is considered overpopulated if it fits $4$ or more birds inside it. How many cages (...
3
votes
1answer
84 views

Compositions of $20$ that have exactly $14$ summands

Question: Prove that for each of the $27132$ of these (compositions of $20$ with exactly $14$ summands), there is always a collection of consecutive summands which sum to $5$. I know that I'm ...
-2
votes
0answers
32 views

What is the maximum number of non-empty subsets in a 20-element set, none of which containing more than two common elements? [duplicate]

What is the maximum number of non-empty subsets in a $20$-element set, none of which contain more than two common elements? I'm stuck on this problem. I guess it has something to do with the ...
1
vote
1answer
46 views

Exercise dealing with pigeonhole principle (even product)

Define $\mathbb{N}_n=\{1,...,n\}$ The pigeon hole principle as I know is that if $n>m$. Then for every map $f:\mathbb{N}_n\rightarrow\mathbb{N}_m$ there exists two distinct $n_1,n_2$ such that $f(...
1
vote
1answer
48 views

Prove that amongst 10 sticks of length 1 to 55 there are 3 that form a triangle

I'm trying to prove, that amongst 10 sticks, which length can vary from 1cm to 55cm, there are 3 (or at least 3), using which one can form a triangle. I feel like I should use Dirichlet's pigeon ...
1
vote
1answer
66 views

Suppose the edges of a complete graph of $10 $ vertices are coloured each either blue or red. Show that there is a blue triangle or a red tetrahedron

Could I get any help with this one, I'm lost. We know that the Ramsey number $R(3, 3)$ equals $6$. Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show ...
5
votes
1answer
91 views

Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$.

Problem : Show that no matter how $12$ points are put on a plane, there are $3$ among them forming an angle not greater than $18^o$. I am not getting any ideas in solving this problem. So, there ...
0
votes
1answer
24 views

Pigeonhole principle about finding a specific group of four people

A bridge club has $10$ members. Every day, four members of the club get together and play one game of bridge. Prove that after two years, there is some particular set of four members that has played ...
0
votes
1answer
79 views

19 arrows hit the target in the form of a regular hexagon page length of 1 m. Show that at least two arrows are less than 60 cm away.

Problem: 19 arrows hit the target in the form of a regular hexagon page length of 1 m. Show that at least two arrows are less than 60 cm away. My attempt: Idea is to use Pigeonhole principle to ...
0
votes
2answers
45 views

105 integers contains a subsequence with sum divisible by 99.

I recently came across a problem which states that $$\\$$ Given any sequence of 105 integers there will always be a subsequence of consecutive elements in the sequence, whose sum is divisible ...
-2
votes
1answer
73 views

Pigeonhole Principle with Sets…consider the set X= { 1, 2, 3, 4,5}… [closed]

I need help with a combo problem. I'm not sure what this is asking and how to begin. Consider the set $X=\{1,2,3,4,5\}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the ...
3
votes
3answers
500 views

A woman selects balls from a bowl at random …

A bowl contains 10 red balls, 10 blue balls and 10 black balls. A woman selects balls at random without looking at them: a) How many balls must she select to be sure of having at least three ...
2
votes
2answers
47 views

Prove by using the Pigeonhole Principle that there are at least $5$ of the $41$ chess pieces on the $10×10$ board that are not on the same row.

There are two ways to prove it. One way is... Consider $41$ chess pieces on $10$ board rows. By using pigeonhole princ., there must be one row that has at least $\lceil{\frac{41}{10}}\rceil$ $=$ $...
1
vote
1answer
44 views

Prove that there exists a set $Y$ such that for every $v$, there exists $y \in Y$ that is incident to $v$.

Suppose $A,B,X$ are independent and disjoint sets of vertices in a graph such that $A \cup B \cup X = V$, $|A|=|B|=9$ and $|X| = 63$. Also, assume $d(v) = 7$ for every $v \in A,B$ and suppose that for ...
1
vote
1answer
50 views

Prove the geometric “Pigeonhole Principle”

This question is part of an introductory combinatorics class, so I don't know what measure theory is, but the question was stated as follows: Suppose $A_1, A_2,... A_k, B$ are sets which contain a '...
-1
votes
2answers
29 views

Pigeonhole Principle Problem - need help understanding the concept

Let $n ∈ \mathbb{N}$ be a natural number and let $X ⊆ \mathbb{N}$ be a subset with $n + 1$ elements. Show that there exist two natural numbers $x, y ∈ X$ such that $x − y$ is divisible by $n$.
0
votes
1answer
55 views

Given any $n+2$ integers, show that there exist two of them whose sum, or else whose difference, is divisible by $2n$.

I came across the following problem when looking at a Putnam practice paper. I saw similar problems on here, but I didn't see the exact one. I would like to know if my proof is valid. Given any $n+2$ ...
6
votes
2answers
118 views

Given three permutations of $\{1,2,\dots,n^3+1\}$, prove two of them have a common subsequence of length $n+1$.

Let $m = n^3 + 1$ and let $\sigma_1, \sigma_2, \sigma_3$ 3 permutations of $\{{1,2,...m}\}$. Prove that two of these permutations have same subsequence which are $n+1$ long. I have tried to use the ...
0
votes
3answers
47 views

Given 20 distinct positive integers, not greater than 70. Show that among their pairwise differences, at least four are equal.

Problem: Given 20 distinct positive integers, not greater than 70. Show that among their pairwise differences, at least four are equal. Solution given by the professor: We may assume that the numbers ...
1
vote
1answer
45 views

Show that the sum or difference of $a_i$ and $a_j$ from a set of seven distinct integers is divisible by 10

I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show? Here's my intuition on how to prove this: $a_i$ and ...
1
vote
1answer
38 views

Deducing divisibility based on Pigeonhole Principle

I am trying to solve this below problem from Norman Bigg's Discrete Mathematics textbook, but cannot reconcile his solution with my work. Let $X$ be a subset of $\{1, 2, \ldots 2n\}$ and $Y$ be ...
0
votes
1answer
42 views

pigeon hole principle [arrangement] [duplicate]

There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to ...
1
vote
1answer
95 views

Dealing with Pigeonhole Principle Problems [closed]

Question: Eleven numbers are chosen from 1, 2, 3, ..., 99, 100. Show that there are two nonempty disjoint subsets of these eleven numbers whose elements have the same sum. Does anyone know how to ...
1
vote
0answers
50 views

Monochromatic triangle - graph coloring

I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a ...
0
votes
1answer
46 views

proof by letters with characters

An authentication system accepts passwords that are composed of lowercase letters from a to z and digits from 0 to 9. Prove that, in this system, given any set of 3000 passwords, there must be at ...
9
votes
1answer
96 views

On $\sup|\varphi^{-1}(n)|=+\infty$

I am trying to find an elementary proof of the following fact: Given some $N\geq 2$, there are $N$ distinct integers $a_1,\ldots,a_N$ such that $\varphi(a_1)=\ldots=\varphi(a_N)$ with $\varphi$ ...
0
votes
2answers
50 views

algorithm problem solving [closed]

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.
1
vote
1answer
44 views

$I$ is a union of intervals such that there do no exist 2 points in $I$ with difference $1/12$.Prove the sum of lengths of intervals is at most $1/2$

Consider $I$ a union of disjoint intervals inlcuded in the interval $[0, 1]$ such that there do no exist 2 points in $I$ situated at distance $1/12$. Prove that the sum of the lengths of the intervals ...
5
votes
5answers
282 views

Splitting a string into 2 parts such that the number of 1's in part A are equal to the number of 0's in part B.

The full question is as follows. Prove that every binary string of length $n$ can be split down into 2 substrings where string $S = A.B$ such that the number of $0's$ in A is equal to the number of $...
1
vote
1answer
152 views

Combinatorics: Prove that $x, y, z$ exist such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$

Suppose we have a subset of $2n-1$ numbers from the set ${1, 2, 3, ..., 2^n-2}$. Prove that there exits $x, y, z$ such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$ I'm fairly new to this topic, ...
1
vote
1answer
72 views

Bob selects four points on a $10\times 10$ square.

Bob selects four points on a $10\times 10$ square. Is it true that two of them are less than $\sqrt{101}$ units apart? I know how to prove things like this for five points. These seems ...
-1
votes
1answer
35 views

how to use the pigeon hole principle on a graph problem? [duplicate]

I have this given problem: In a class there is 6 students,every 2 students of 6 know each other in advance or they don't. Show that there is 3 students that don't know each other in advance or that ...
0
votes
0answers
55 views

A deck of cards and the Pigeonhole Principle

I am trying to solve the following problem: How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds? It isn't ...
1
vote
1answer
29 views

Question on a proof of no existance of monochromatic triangle in any tricoloring of edges of $K_{16}$

Here is a question on the book "Problem -Solving Strategies" by Arthur Engel, with a provided solution: In the solution, they partitioned the abelian group into 3 sets such that none of them is sum-...