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
-8
votes
0answers
36 views

Pigeonhole principle Exercise. There are 25 students participate in the course ... [closed]

I do really have no time to solve the task. I would highly appreciate if you could send me the solution. There are 25 students participate in the course. Each of these people studies in the first, ...
2
votes
2answers
137 views

Show: For any $n+1$ integers chosen from $[1,2n-1]$, there are $3$ numbers chosen such that the sum of two of them gives us the third number

Let $n$ be a positive integer, and let $S$ be a set of $n+1$ integers in $[1,2n-1]$. Then show that there are $3$ numbers in $S$ such that the sum of two of them gives us the third number (the ...
0
votes
2answers
64 views

Confirmation in one step involved in solving 'Show that any 2 of 3 integers chosen randomly satisfy $10|a^3b - ab^3$.

After factoring: $ab(a-b)(a+b)$ gives that it is always multiple of 2 so I only need to prove it is multiple of 5. For that I made a set $A={a,b,c,(a-b),(a+b),(b-c),(b+c),(c-a),(c+a)}$ By pigeon hole ...
1
vote
3answers
86 views

Minimum number of holes such that each of 160 pigeons fly in different hole with a condition

PROBLEM STATEMENT : Suppose there are $160$ pigeons and $ n$ holes. The first pigeon flies to the $1st$ hole, the second pigeon flies to the $4th$ hole, and so on, such that the $i^{th}$ pigeon flies ...
0
votes
2answers
60 views

Solving a problem using the Pigeonhole principle

How do I use the Pigeonhole principle to show that in a class of 25 students where every student is either a sophomore, freshman or a junior there are at least 9 sophomores or 9 seniors or 9 juniors ? ...
2
votes
2answers
104 views

To find the minimum number of $3$-toppings pizza so that it meets the demand of my friend!

In a pizza shop they are offering $3$-toppings pizza with $10$ choices of toppings. A friend has decided that two of the three toppings on the pizza must be what they want but I don't know which two ...
0
votes
0answers
42 views

Points on a $m\cdot n$ grid with no right triangles formed

In an $m \cdot n$ rectangular grid of points, $k$ points are marked, such that no three marked points form a right triangle with legs parallel to the sides of the rectangular grid. What is the ...
5
votes
1answer
60 views

Showing there is a node in the graph with only one edge

I saw this question recently, Showing there is a node in the graph with one and only one edge and I am just wondering how the approach would be different if we added the following restraint: We have ...
-1
votes
1answer
47 views

Uniqueness of $y$ in $xy \equiv 1 \pmod{p}\,$? [duplicate]

Let $Q = \{1, 2,\dots, p −1\}$ for some prime $p$. Is it possible to use the pigeonhole principle to prove that for each integer $x \in Q$, there is precisely one integer $y \in Q$ such that $xy \...
0
votes
1answer
74 views

Pigeonhole Principle: Among any seven integers, there must be two whose sum or difference is divisible by $10$

So, I am studying computer science (bachelor). This is actually my third degree (bachelor and master in management previously). I'm new to discrete mathematics, but I find as useful as fascinating.(I ...
5
votes
3answers
122 views

Combi Problem - Proving Existence of a row

The following problem comes from a Problem Set that concluded recently - Problem: $50$ girls and $50$ boys stand in line in some order. There is exactly one stretch of $30$ children next to each other ...
3
votes
0answers
36 views

Graph Theory Pigeonhole Principle Question [duplicate]

Question: Suppose that G is a graph such that any two vertices in G that have the same degree are not connected to any of the same vertices. In other words, vertices with the same degree don't share ...
0
votes
1answer
34 views

Show that if four distinct integers are chosen between $1$ and $60$ inclusive, some two of them must differ by at most $19$

I am trying to understand this question. This is from the book Essential Discrete Mathematics for Computer Science and Question is from Chapter one "the pigeonhole principle" So clearly we ...
6
votes
1answer
154 views

Showing there is a node in the graph with one and only one edge

We have an undirected simple graph with $n$ vertices where for every pair of vertices $v_1,v_2$, if $d(v_1)=d(v_2)$ then the set of neighbours of $v_1$ is disjoint from the set of neighbours of $v_2$. ...
1
vote
0answers
36 views

Show that in any set of 9 positive integers, some two of them share all of their prime factors that are less than or equal to 5

The proof that i came up is as follows. Assume any non prime positive integer${}> 1$ will have factors of either $2,3,5$ or a combination of them. Let $S$ be a set of sets where each set conatians ...
2
votes
0answers
39 views

Finding a pair of divisors in a set of $n+1$ integers

I am trying to solve the below problem without using induction. Consider a set of $n+1$ positive integers, each less than or equal to $2n$. Show there must always exist a pair of integers in the set, ...
0
votes
1answer
48 views

What does the pigeonhole principle have to do with graph theory?

I am currently trying to teach myself graph theory, and in every book I've read the pigeonhole principle inevitably comes up. I understand the concept well enough, but what I fail to grasp is what a ...
1
vote
0answers
36 views

Given $n^2 +1$ points on Euclidean plane, construct a monotone curve passing through at least n points

Given $n^2+1$ points on a Euclidean plane, I have to prove that there exists a monotone curve passing through at least n of these points. My intuition pigeon hole principle has to be used to solve the ...
4
votes
1answer
254 views

Pigeonhole principle: Coloring $11$ points of a $5\times 5$ square grid

We have a $ 5 \times 5$ grid of points, all colored white. Now 11 of the 25 points are colored black. Prove that it is possible to find 3 points all colored black such that no two of them share the ...
0
votes
0answers
27 views

Show that in every set of 201 positive integers, each less than 301, there are two, the ratio of which is a power of 3

I tried to play around with the question and came up with some (possibly wrong) observations. Firstly, I noticed that for there to be a ratio which is a power of 3, you must have $\frac{a}{b} = 3^n$. ...
0
votes
2answers
46 views

Verifying a proof of a combinatorics problem

today I attempted this problem and have a proof I am not sure is correct. Show that given any 52 integers, there exist two of them whose sum, or else whose difference is divisible by 100 Firstly it ...
1
vote
1answer
51 views

Use the pigeonhole principle on a triangle

Question: There is a castle shaped like an equilateral triangle. The length of each side of the castle is $200$ meters. Five guards are placed around the perimeter of the castle spaced as far apart as ...
0
votes
1answer
72 views

Pigeon Hole Principle for a triangle [closed]

Within, an equilateral triangle whose length of each side is 200 meters. Five metropolitan police officers guard the garden taking a position as far away from each other as possible to cover more. ...
-3
votes
2answers
43 views

Show that given a subset of 10 consecutive integers show that there are at least 2 subsets with the same sum

How do I show this? I can't think of any possible way. I assume I should use the principle but don't know how
0
votes
0answers
18 views

Pigeonhole principle on an integral

This question is from the Lemma 1.2.8 of the book Higher order fourier analysis by T. Tao. We use the following notations: $[N]:=\{1,2,\cdots,N\}$ $\mathbb{E}_{n\in [N]}f = \frac{1}{N}\sum_{n \in [N]}...
3
votes
2answers
102 views

For any unbounded set of real numbers, is there a subset which almost coincides with a uniformly spread out set of points an infinite amount of times?

I figured out yesterday that, given an unbounded infinite sequence $\ (\alpha_n)_{n\in\mathbb{N}}\subset \mathbb{R}\ $ with $\ \alpha_i \neq \alpha_j\ $ if $\ i\neq j\ $, there does not necessarily ...
0
votes
0answers
59 views

Need help with this problem(mp based on PigeonHole Principle)

given a set S with distinct elements $s_{0}, s_{1},s_{2}.. s_{99}$, $s_{i} \in [0, 10^6] $ we have to construct 100 sets T1,T2,T3,T4.. T100, such that $ T1=[s_{0}+t_{1},s_{1}+t_{1},s{2}+t_{1},... ,...
2
votes
0answers
26 views

Fourier in $\mathbb{Z}^d$ and use of Pigeonhole principle (Prop. $1.1.13$, HOFA by T. Tao)

We use the following notation: $$[N]:=\{1,2,3,\cdots,N\}$$ $$\mathbb{E}_{n\in [N]}f(x) : = \frac{1}{N}\sum_{n \in [N]}f(x)$$ This doubt is from the book titled Higher Order Fourier Analysis by T. Tao. ...
0
votes
1answer
20 views

Minimum number of chopsticks to get 4 pairs with same colors

There are 6 pieces of white chopsticks, 8 pieces of yellow chopsticks, and 10 pieces of blue chopsticks mixed together. If you want to get 4 pairs of chopsticks with the same colors in dark, at least ...
4
votes
1answer
71 views

Find the smallest natural number $n$ such that every $n$-element subset of $S=\{1,2,\dots,280\}$ contains $5$ pairwise relatively prime numbers

A friend gave me the following question to solve- Let $S=\{1,2,\dots ,280\}$. Find the smallest natural number $n$ such that every $n$-element subset of $S$ contains $5$ pairwise relatively prime ...
-1
votes
1answer
200 views

How do i find the number of gangs in this question?

Question) Let us define a gang of integers as integers that are formed by rearranging the digits in the decimal representation of a positive integer. Example #1: 1123, 1213, 1231, 2113, 2131, 2311, ...
4
votes
1answer
63 views

If you sum all possible subsets of peoples' birthday dates in a group of 7 people, will two sets always have the same sum?

Suppose for a set $S$ of 7 people, $f(s)=$ the birthday date of the person for each person in $S$. For example if their birthday is May 17th then $f(s)=17$. Now for every subset $T \subset S$ let $g(T)...
1
vote
1answer
72 views

Proof via pigeonhole principle

Consider the terms with base five with non-negative powers: $5^0, 5^1, 5^2, ……$ Prove using the pigeonhole principle that there are two of these terms which differ by a multiple of 2021. So far from ...
0
votes
0answers
62 views

Explain why two students will have shaken the same number of hands.

Question: Twenty-five students attend a class reunion and shake hands with each other. If no student shakes hands with the same person twice, explain why two students will have shaken the same number ...
0
votes
0answers
20 views

Is this solution to a seating / PigeonHole question correct?

The question asks: Suppose there are 1350 people seated in a row of 2021 chairs. Prove that there are 3 consecutive non-empty (taken) chairs. Here was my logic: Assume (by contradiction) that the ...
0
votes
1answer
52 views

Pigeonhole's Principle - set of nine distinct points

The question is "Let $(x_i , y_i , z_i ), i = 1, 2, 3, 4, 5, 6, 7, 8, 9,$ be a set of nine distinct points with integer coordinates in $xyz$-space. Show that the midpoint of at least one pair of ...
1
vote
2answers
68 views

How does pigeonhole principle imply that $|\theta_k-\theta_j|\leq 2\pi/N<\delta$ where $\theta_k=(k\theta)\mod 2\pi$

I am trying to understand this part from the book Page 196, Quantum Computation and Quantum Information by Nielsen and Chuang. Here $R_{\hat{n}}(\theta)=\cos(\theta/2)I-i(\hat{n}.\vec{\sigma})\sin(\...
0
votes
0answers
77 views

Let $n$ be odd and supposed $(x_1,x_2,...,x_n)$ is any permutation of $\{1,\ldots,n\}$. Prove that the product $(x_1-1)(x_2-2)\ldots(x_n-n)$ is even.

Is the result necessarily true if $n$ is even? Give a proof or counterexample. For the first part, we know $n$ is odd so we let $n = 2m + 1$. Then let $F = (x_{1},...,x_{n})$, and $S = \left\{a\, | \,...
0
votes
1answer
42 views

Dirichlet's approximation theorem for two numbers

Show that $∀ x_1, x_2∈ (0,1)$, there exists integers $1 \leq q \leq 100$ and $0\leq p_1, p_2 \leq q$ such that $|x_1-\frac{p_1}{q}| \leq \frac{1}{10q}$ and $|x_2-\frac{p_2}{q}| \leq \frac{1}{10q}$ I'...
2
votes
2answers
82 views

Maybe pigeonhole principle

Given any $10$ people in a room, prove that among them there are either $3$ that know each other or $4$ that do not know each other. (Assume that if A knows B, then B knows A.) Could the pigeonhole ...
0
votes
1answer
52 views

Help with understanding Pigeonhole Principle concepts

I'm currently reading Discrete Mathematics - G. Chartrand & P. Zhang and I'm having trouble with understanding two concepts with the Pigeon Principle that are explained in the textbook: For given ...
0
votes
1answer
57 views

how many points inside rectangle so distance is $0<d\leq \sqrt{2}$.

Given a rectangle with dimensions $m$ inches and $n$ inches. How many points inside that rectangle have to be chosen to make sure that two of them have distance $d$ with $0 < d \leq \sqrt{2}$? Here ...
0
votes
1answer
49 views

pigeonhole what are the parts of the proof using the pigeonhole principle?

We can divide a proof by induction in two parts: Inductive base and Inductive step. One proves for the case when n = 1, and after one suppouse what we want to prove is the case for an arbitrary k, ...
1
vote
0answers
60 views

For $n$ an odd positive integer. Select $x,y$ distinct from $\{1, 2, \dots, n\}$ with $x+y = n+1$.

Question: Let $n$ be some odd, positive integer and $S = \{1,2,\dots, n\}$. Show that if $\frac {n+3}2 $ numbers are selected from $S$, then there will be distinct numbers $x,y$ in that selection such ...
0
votes
0answers
35 views

What's the minimum value of $f\in{S}$

Let $S$ be the collection of all $n-uplets$ of natural numbers ($x_1,x_2,...,x_n$) such that their sum is equal to $2000$. We assosiate to each $n-uplet$ ($x_1,x_2,...,x_n$)$\in{S}$ the number $f((x_1,...
1
vote
0answers
67 views

Every $2$-colouring of the lattice points of $\mathbb R^m$ has $n$ monochromatic points whose centroid is a lattice point of the same colour

I was asked the question Prove 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 Now, ...
0
votes
2answers
53 views

Pigeons in multiple holes (solution explain)

Problem: Seven people sit at a round table with 10 chairs. Show that there are three consecutive chairs that are occupied. Solution: Number the chairs from 1 to 10. There are 10 groups of three ...
1
vote
1answer
40 views

Pigeonhole Principle problem regarding a set of numbers and two subsets [duplicate]

I have a question for one of my CSI classes and I've never been taught the material before so I'm completely stuck. The problem asks to take a set of 12 positive integers (not necessarily distinct) ...
6
votes
1answer
227 views

Pigeonhole: 200 Balls into 101 Bins

I found the following question on this website: You have 200 monkeys placed in 101 spaceships such that each spaceship contains at least one monkey. Prove there is a subset of spaceships containing a ...
0
votes
3answers
66 views

Show that at least 4 of any 22 dates in the calendar must fall on the same day of the week

Show that at least 4 of any 22 dates in the calendar must fall on the same day of the week I have a question regarding this proof. When we assume the opposite is true, that is, assume that no more ...

1
2 3 4 5
28