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,364 questions
Filter by
Sorted by
Tagged with
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, ...
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 ...
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 ...
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 ...
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 ? ...
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 ...
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 ...
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 ...
47 views

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

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 ...
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 ...
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 ...
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 ...
68 views

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'...
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 ...
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 ...
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 ...
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, ...
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 ...
35 views

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 ...
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) ...