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
0
votes
1answer
22 views

Permutations with pigeonhole principle quesion

I have set G of 101 functions from [10] to [10] ([10] is S10). I need to prove that there are 2 functions (a,b) from the set G, and two numbers I,j that belongs to [10], that sustain a(i) = b(i) and a(...
3
votes
2answers
35 views

Proof by contradiction of a variant of PHP

Let $a_1, a_2,\ldots , a_n$ be positive integers. Prove that if $(a_1+a_2+\ldots+a_n)-n+1$ pigeons are to be put in $n$ pigeonholes, then for some $i$, the statement "The $i^{th}$ pigeonhole ...
7
votes
2answers
76 views

If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$.

$\blacksquare~$ Problem: If $15$ distinct integers are chosen from the set $\{1, 2, \dots, 45 \}$, some two of them differ by $1, 3$ or $4$. $\blacksquare~$ My Approach: Let the minimum element chosen ...
-5
votes
0answers
30 views

Math Question - Pigeonhole-Principle [closed]

Vera has $10$ white socks, $10$ black socks, $10$ brown socks, $10$ blue socks, and $10$ red socks. How many socks (at a minimum) must she pull out of her sock drawer to ensure at least two matching ...
-1
votes
2answers
77 views

Show that for every integer $n$ there is a multiple of $n$ that has only $0s$ and $1s$ in its decimal expansion.

Can anyone please explain this example as I tried a lot to understand it but I can't! The problem: Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal ...
1
vote
2answers
38 views

How many vertices with same degree

In a simple graph with $2000$ vertices without any vertex with $\deg(a)=0$, we have exactly two vertices which have the same degree. What is the degree of these two? I think I should use pigeon hole ...
3
votes
3answers
66 views

Pigeonhole Principle Proof and Existence

So, I’m going through a textbook on combinatorics, and I came across this exercise question. Let $n$ be odd, and suppose $(x_1, x_2, \dots, x_n)$ is a permutation of $[n].$ Prove that the product of $...
4
votes
0answers
62 views

$S \subseteq \mathbb{N}$ and $\forall k \exists x : \forall i,j \in S, |i-j| \notin [x,x+2^k].$ Prove $S$ has zero density in $\mathbb{N}.$

$S \subseteq \mathbb{N}$ and $\forall k \in \mathbb{N},$ there exists $x$ (depending on $k$) such that $\forall i,j \in S,$ we have $|i-j| \notin [x,x+2^k].$ How do I show that the density of $S$ in $\...
1
vote
2answers
47 views

Problem about the generalized pigeonhole principle

This problem from Discrete Mathematics and its application's for Rosen What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10-...
0
votes
1answer
73 views

Putnam Pigeonhole principle problem regarding a 20 person college and 6 courses

Question: A certain college has 20 students and offers 6 courses. Each student can enroll in any or all of the 6 courses, or none at all. Prove or disprove: there must exist 5 students and 2 courses, ...
3
votes
4answers
147 views

Proving that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$

How can one prove that among any $2n - 1$ integers, there's always a subset of $n$ which sum to a multiple of $n$? It is not hard to see this is equivalent to show that among $2n-1$ residue classes ...
-1
votes
0answers
58 views

36 cards were distributed equally to 6 people. Prove that there is a person who has at least 4 cards of the same suit

36 cards were distributed equally to 6 people. It is known that for any two people there are at least two suits, such that they have equal cards of these suits. Prove that there is a person who has ...
-1
votes
2answers
58 views

Is this a violation of the Pigeonhole Principle?

Given a set $S$ of elements [1, to 21] generate a list of permutations fixed to a constant of $3$. $P(n,r)$=$P(21,3)$ $=21!/(21−3)!$ $= 7980$ possible permutations of 3-element sets Fact: There are $...
0
votes
3answers
72 views

Show that if 12 integers are chosen there are always two whose sum or difference is divisible by 20. [closed]

Also, prove that this is sharp, i.e., one can pick 11 integers so that the sum or the difference of any two of the chosen integers will never be divisible by 20. I'm trying to solve this problem using ...
3
votes
1answer
87 views

$4$ vectors in $\mathbb{Z_4}^9$that sum to $0$. [duplicate]

Problem: Given $2018$ elements not necessarily distinct from $\mathbb{Z_4}^9=\mathbb{Z_4} \times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{Z_4}\times \mathbb{...
0
votes
2answers
55 views

What is the minimum $N$ such that if $N$ people discuss three topics, then at least three people will discuss the same topic? [closed]

$N$ people corresponded by mail with one another, each corresponding with all of the rest. In their letters, only three topics were discussed. If we can always find at least three people who discussed ...
0
votes
1answer
108 views

Use Induction to solve a $\bmod$ question.

On a holiday my $m \in \mathbb{N}, m \geq 1$, many of my family members gave me $a_m \in \mathbb{N}$ much money. Here $a_m$ implies the amount each family member gave. Let's say that a computer game ...
0
votes
1answer
64 views

In a math competition with $8$ students and $8$ problems, if each problem is solved by $5$ students, then two students together solve all problems. [closed]

Eight students are entered in a math competition. They all have to solve the same set of $8$ problems. After correction, we see that each problem was correctly resolved by exactly $5$ students. Show ...
5
votes
1answer
112 views

A 10x10 table filled with 0 to 9 numbers

I saw this question but I couldn't find the answer. Assume that we have a 10x10 table, and it's filled with 0 to 9 numbers ( 10 of each of them are in the table, 10x zero, 10x one, and ... ) By using ...
7
votes
2answers
84 views

$S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ prove either $|S_i \cap S_j| \ge 5$ or $|S_i^C \cap S_j^C| \ge 5$ for some $i,j.$

Given subsets $S_1, \dots, S_6 \subseteq \{1,2,\dots,21\},$ I wish to prove either $|S_i \cap S_j| \ge 5$ or $|S_i^C \cap S_j^C| \ge 5$ for some $i \ne j.$ I started off by assuming $|S_i^C \cap S_j^C|...
0
votes
2answers
41 views

Pigeonhole principle - Octahedron question

So I came across a pigeonhole principle question and was unable to complete this question. I was just wondering how to commence this question/what sort of reasoning I could use to "explain". ...
1
vote
1answer
167 views

Integer solutions of a system of equations: $a_{11}x_1 +a_{12}x_2 + \ldots+ a_{1q}x_q = 0$, $\ldots$, $a_{p1}x_1+a_{22}x_2+\ldots+a_{pq}x_q = 0$

Let $q = 2p$, where $p$ is a positive integer. The following is a system of equations $$a_{11}x_1 +a_{12}x_2 + \cdots+ a_{1q}x_q = 0\\a_{21}x_1+a_{22}x_2+\cdots+a_{2q}x_q = 0\\\vdots\qquad\qquad\...
2
votes
3answers
106 views

In a $n \times n$ grid of points, choosing $2n-1$ points, there will always be a right triangle

$\textbf{Question:}$ Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always be a right triangle with vertices among these $2n-1$ points. This ...
0
votes
0answers
53 views

|Discrete Mathematics |The pigeonhole principle + Euclid algorithm?

We've been given in class of Discrete mathematics a problem which we have to prove using the Pigeonhole principle. I've been at it for quite a while. Problem is, English is not my first language and ...
3
votes
2answers
44 views

Pigeonhole Problem with Subsets

Let $S$ be an arbitrary subset of $\{1, 2, ..., 99\}$ with $|S|=10$. Prove that there are two different subsets $A$ and $B$ (don't have to be disjoint) of $S$ so that $$\text{the sum of all the ...
3
votes
0answers
41 views

Apply Pigeonhole Principle to pick numbers such that at least two of them have a digit in common

How many integers from 100 through 999 must you pick in order to be sure that at least two of them have a digit in common? (For example, 256 and 530 have the common digit 5.) In the worst case I ...
1
vote
1answer
63 views

Given $372$ points in a circle with a radius of $10$, there is an annulus with radii $2$ and $3$ containing at least $12$ of these points.

Given $372$ points in a circle with a radius of $10$, show that there is an annulus with inner radius $2$ and outer radius $3$, which contains not less than $12$ of the given points. My thinking is ...
2
votes
1answer
50 views

Prove the difference is more than $n$ and less than $2n$

We chose $n + 2$ numbers from the set $\{1,2,....3n\}$ . Prove that there are always two among the chosen numbers whose difference is more than $n$ but less than $2n$. Though I can understand it by ...
3
votes
1answer
59 views

Proving that some integer multiple of a real number is within $\frac{1}{k}$ of an integer.

So I'm trying to prove that for every real number $a \in \mathbb{R}$, the set $M = \{a,2a,\dots,(k-1)a\}$ contains at least one element that is within $\frac{1}{k}$ of an integer. (Note that $k \in \...
3
votes
2answers
86 views

USSR MO 1980 pigeonhole-principle [closed]

Let $n \geq 3$ be an odd number. Show that there is a number in the set $\{2^1-1,2^2-1,...,2^{n-1} - 1\}$ which is divisible by $n$.
3
votes
1answer
42 views

Prove that L has four elements , the product of which is equal to the fourth power of an integer

The set $L$ consists of 2003 integers , none of which has a prime divisor larger than $24$. Prove that $L$ has four elements , the product of which is equal to the fourth power of an integer. Above ...
0
votes
2answers
34 views

understanding a pigeonhole principle problem

I am trying to understand an already solved problem which makes use of the pigeonhole principle There are $271$ students in an exam which consists of $3$ random, non-repeating questions out of a ...
0
votes
1answer
48 views

pigeonhole principle cube problem

i got this problem that we need to prove that we cannot pick 28 points that are 1.75cm(atleast) from eachother in a cube where each edge is 3cm long . i tried $dividing$ each square in the cube to $...
0
votes
0answers
46 views

Does this generalization of the pigeonhole principle have a name of its own?

Is there any name for the fact that for any pair of finite sequences of real numbers $(a_i)_{i=1}^n$, $(b_i)_{i=1}^n$ there is $k \in [1,n]$ such that: $$a_k \cdot \sum_{i=1}^n b_i \geq b_k \cdot \...
2
votes
0answers
46 views

Pigeonhole principle of 81 numbers [closed]

Please someone can help me to prove this. We have a 9x9 square panel with some arrangement of the numbers 1... to 81 in it. Prove that there are at least two neighboring numbers the differnce between ...
1
vote
2answers
91 views

For what percentage of numbers does this proof of Goldbach's conjecture hold?

Question For what percentage of numbers does the below inequality hold? $$ \pi(2m) > \frac{\phi(2 m) -1}{2} $$ where $m$ is not a prime or $1$, $\pi(m)$ is the number of primes less than $m$ and ...
1
vote
1answer
53 views

Prove that if there is 44$ bill and 10 people to split the bill, then at least two people paid the same amount of money.

I'm learning how to do proofs and now trying to prove the following statement: Suppose you are having dinner with nine friends and want to split the bill, which is $44. Everyone pays in dollar ...
0
votes
2answers
38 views

Prove that there is either a red triangle whose vertices are in S, or a set of 4 points in S such that

Take any set S of 10 points in the plane in which no three are colinear. Color each of the $\binom{10}{2}$ line segments between two of these points with one of red or blue. Prove that there is either ...
0
votes
1answer
28 views

is given. prove that there is 3 numbers a, b, c that: $0.5<$a^2/bc<2 using pigeonhole principle.(n>2) [closed]

$2n-1$ numbers from {${1, 2, 3, ...,2^n-2}$} is given. prove that there is 3 numbers a, b, c that: $0.5<$a^2/bc<2 using pigeonhole principle.(n>2) we do not know which numbers selected. a, b, c ...
1
vote
1answer
77 views

Prove any set S of three integers contains a pair $x\neq y$ such that $x^3y-xy^3$ is divisible by 10.

Prove any set S of three integers contains a pair $x\neq y$ such that $x^3y-xy^3$ is divisible by 10. My attempt was : By the division algorithm, every integer $n$ can be written as $n = 10q + r,$ ...
0
votes
1answer
36 views

Explain why there may not be $3$ people with same car.

I don't really understand how to apply Ramsey Theory or the Pigeonhole Principal, so I can't see why this is true: There are $100$ people at a party. Assume each person has an even number of cars, ...
1
vote
3answers
51 views

Understanding the mathematical definition of The Pigeonhole Principle.

The Pigeonhole Principle states that if you have $n$ pigeons and $n-1$ pigeonholes, then at least one of those holes must contain at least $\lceil{\frac{n}{n-1}}\rceil$ many pigeons. So if you have $3$...
1
vote
4answers
39 views

Prove that among any 111 randomly chosen integer numbers there is either one which is a multiple of 111 or two whose difference is a multiple of 111. [closed]

Prove that among any 111 randomly chosen positive integer numbers there is either one which is a multiple of 111 or two whose difference is a multiple of 111. This was a question I had on a test. I ...
2
votes
1answer
42 views

Prove That Every Simple Graph Has Two Vertices Of The Same Degree.

This is my solution to the problem I just need help verifying if my solution is correct or not.
0
votes
0answers
25 views

Proof with pigeonhole principle in sets and numbers

Let $S=\{-n,-n+1,-n+2,...,-1,0,1,...,n-1,n\}$ and $T$ is a subset of $S$ that has $n+2$ elements. Prove that there are $3$ numbers like $a,b,c\in T$, such that the relation between them is $c=b+a$.
1
vote
1answer
33 views

prove 3 separate subsets of 90 numbers with similar sums

"Given a set of 90 numbers , each with 3 digits , prove that there exist 3 subsets which are each separate , that have the same sum (sum of the numbers)." I know that I should use the pigeonhole ...
0
votes
3answers
44 views

Questions About A Pigeonhole Principle Problem

I've encountered the following pigeonhole principle problem. It uses notation from set theory, which is a subject I haven't studied yet. I would like to check if I have understood notation, and the ...
0
votes
1answer
32 views

Discrete Mathematics - Pigeon Hole Principle/ Geometry combinatrix

I am trying to solve a problem that states a certain number of points lets say 50, are in a 20cm cube. It then asks to prove that 7 are in a 10cm cube. How is this even pigeonhole? I've not done this ...
1
vote
3answers
61 views

Question About A Problem Involving The Pigeonhole Principle

I am trying to solve the following problem, from the following collection of problems involving the pigeonhole principle: https://cemc.uwaterloo.ca/events/mathcircles/2018-19/Winter/Senior_Feb27.pdf - ...
1
vote
1answer
30 views

How many integers do we need to select from a set from 1 to 20 to guarantee there will be two of the same pairwise sum?

What is the intuition for this? I currently know that there are 38 possible sums, and I'm stuck after that. Any intuition would help, thanks!

1
2 3 4 5
23