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

learn more… | top users | synonyms

2
votes
2answers
287 views

The decimal expansion of the quotient of two integers

It is an exercise in a book on discrete mathematics.How to prove that in the decimal expansion of the quotient of two integers, eventually some block of digits repeats. For example: $\frac { 1 }{ 6 } ...
2
votes
2answers
97 views

Prove using Pigeon Hole principle.

A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, to avoid tiring himself, he decides not to play more than 12 games during any calendar ...
2
votes
2answers
103 views

show that at least 3 balls have same weight

You are given 49 balls of colour red, black and white. It is known that, for any 5 balls of the same colour, there exist at least two among them possessing the same weight. The 49 balls are ...
2
votes
2answers
140 views

Solve using Pigeonhole principle

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44. How can I prove this using pigeonhole ...
2
votes
1answer
569 views

Pigeonhole Principle on Graphs

I just have a last minute question for my combinatorics final (which is in one hour!!). My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole ...
2
votes
2answers
273 views

Question about the Pigeonhole Principle

The question is: Let $A = \{1,2,3,4,5,6,7,8\}$. If five integers are selected from $A$, must at least one pair of the integers have a sum of $9$? The book explains the solution by dividing the ...
2
votes
2answers
704 views

Maximum number of mutually orthogonal latin square pairs (definition provided)

An $n\times n$ matrix is defined to be a "latin square" if each row and column is a permutation of the first $n$ natural numbers. Two squares of same order are orthogonal if the $n^2$ pairs ...
2
votes
2answers
462 views

Pigeonhole principle question confusion

Now I understand it. I just learnt this principle. I am doing a problem in which there's a box with many red socks, green socks and blue socks. First question was how many minimum socks should I pick ...
2
votes
1answer
60 views

$5$ points on a sphere [duplicate]

Diffuse $5$ points on a sphere. Prove there is a closed half-sphere that has at least $4$ points on it.
2
votes
2answers
129 views

Show that some 5 consecutive chairs must be occupied.

A group of 25 people are seated in a row of 30 chairs. Show that some 5 consecutive chairs must be occupied.
2
votes
2answers
756 views

Selecting from $\{1,2,3,4,5,6,7,8,9\}$ to guarantee at least one pair adds to $10$

How many numbers must be selected from the set $\{1,2,3,4,5,6,7,8,9\}$ to guarantee that at least one pair of these numbers add up to $10$? Justify your answer. Here's my answer. Consider the ...
2
votes
1answer
973 views

Pigeonhole Principle Question: Given any 5 points inside a square of side length 2, there is always a pair whose distance apart is at most $\sqrt2$

The question I am looking at: Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$. This looks to me like I ...
2
votes
3answers
262 views

Pigeonhole Principle -

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. Show that the number \begin{equation}x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))\end{equation} is even. I don't understand ...
2
votes
1answer
349 views

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to ...
2
votes
4answers
2k views

Pigeonhole principle: show that a class of nine has at least five male or five female students.

Here is the problem in full, start to finish, with no other special instructions or rules: "If there are 9 students in a class, show that at least 5 must be male or at least 5 must be female. Also, ...
2
votes
2answers
227 views

how to apply hint to question involving the pigeonhole principle

The following question is from cut-the-knot.org's page on the pigeonhole principle Question Prove that however one selects 55 integers $1 \le x_1 < x_2 < x_3 < ... < x_{55} \le 100$, ...
2
votes
3answers
45 views

existence of a lattice rectangle in a $13 \times 13$ grid

Problem: Prove that if 53 points are chosen from a $13\times 13$ grid then there will necessarily exist a rectangle whose vertices are among the 53 points chosen. My try: I am guessing we have to ...
2
votes
1answer
52 views

Are Square and equilateral triangle the only convex regular ngons that can be composed to smaller versions of themselves?

While I was trying to make an analogous question to Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\frac{\sqrt{2}}{n}$ apart, using equilateral ...
2
votes
2answers
94 views

Candidates in an exam

443 candidates enter the exam hall. There are 20 rows of seats I'm the hall. Each row has 25 seats. At least how many rows have an equal number of candidates. My attempt Seat 25 in the first row 24 ...
2
votes
1answer
158 views

Pigeonhole Principle / Number Theory

Let $S$ be a subset of $A=\{1,2,3,...,1000\}$. Find the largest number of elements in $S$ such that for any $a, b \in S$ with $a>b$, $a-b$ does not divide $a+b$. I've tried numerous approaches, ...
2
votes
1answer
164 views

An interesting problem using Pigeonhole principle

I saw this problem: Let $A \subset \{1,2,3,\cdots,2n\}$. Also, $|A|=n+1$. Show that There exist $a,b \in A$ with $a \neq b$ and $a$ and $b$ is coprime. I proved this one very easily by using pigeon ...
2
votes
1answer
177 views

Using the Pigeonhole Principle to show that $2$ of any $n+1$ numbers from $\{1,2,\ldots,2n\}$ sum to $2n+1$

Let n be greater or to 1, and let S be an (n+1)-subset of [2n]. Prove that there exist two numbers in S whose sum is 2n+1. I know I have to use the pigeonhole principle - no idea how to start...
2
votes
1answer
202 views

Twenty distinct integers are chosen from {1,2,…,69} and their differences

Twenty distinct integers are chosen from {1,2,...,69}. Prove that amongst their pairwise differences there are at least four which are identical. I understand that the set {1...69} is ...
2
votes
1answer
81 views

Combinatorics problem; counting in two ways, china 1993

I'm trying to solve the combinatorics problems provided in Yufei Zhao's blog. Can you help me with this one? China (1993): A group of $10$ people went to a bookstore. It is known that ...
2
votes
1answer
79 views

Pigeon-Hole Principle Common Sum

Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the ...
2
votes
1answer
95 views

Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

$n$ is also given to be an even number. So I want to prove this by using the pigeon-hole principle. I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as ...
2
votes
2answers
216 views

Is this question a pigeon hole question?

How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15? Explain. It seems like this is similar to the birthday pigeon hole ...
2
votes
1answer
278 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
2
votes
2answers
109 views

Any two points inside a circle are within a diameter of each other.

In many problems involving the Pigeonhole Principle, we often assume the following lemma: Lemma: The distance between any two points in a circle of radius $r$ is at most $2r$. Intuitively, this ...
2
votes
2answers
660 views

Extended Pigeonhole Principle: How to prove it?

A version of the pigeonhole principle is: (1) If m objects are put in n boxes and n < m, then at least one box contains at least ceil(m/n) objects An alternate (more generalized) version ...
2
votes
2answers
150 views

Pigeonhole Principle Exercise

Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$. I think it is doable using the Pigeonhole Principle.
2
votes
2answers
74 views

A combinatorics problem

Given $A = \{a_0, a_1,...,a_m\}$ such that it's a subset of $\{1,2,...,n\}$ where $m>n/2$, and $a_0$ is the smallest number in $A$. Show that $A$ contains two numbers $b$ and $c$ such that ...
2
votes
2answers
179 views

Pigeonhole-principle with two choices

I am able to solve this sort of problem pretty easily. An arm wrestler is the champion for a period of 75 hours. The arm wrestler had at least one match an hour, but no more than 125 total ...
2
votes
1answer
68 views

Prove that if a graph has six vertices, then at least one of G or $\bar{G}$ has a subgraph isomorphic to $K_3$

I think this proof is related to proving to Theorem on friends and strangers which can be proved with the pigeonhole principle. But I am at a loss as to what are the holes and pigeons in this case. I ...
2
votes
2answers
98 views

Chords of a 20-gon

Twenty points lie on a circle, so as to form a regular polygon. Then they are split into ten pairs, and the points in each pair are connected by a chord. Prove that some pair of these chords have the ...
2
votes
1answer
50 views

Seems straightforward pigeonhole

If we are given $37$ integers then show that it is possible to choose $7$ of them with sum divisible by $7$. I have tried this problem but with no avail. If we assume there are no integers with ...
2
votes
1answer
82 views

pigeonhole principle question 40 participants in an art workshop

There are 40 participants in an art workshop. Each one of them signed up for one or more of the following courses: handicraft, ceramics and Chinese paintings. One of the combinations of courses must ...
2
votes
4answers
174 views

Pigeonhole principle for dominoes.

Suppose we have 13 dominoes, each with a red and blue integer number. Prove that there is a subset of 4 dominoes such that the sum of the 4 red numbers and the sum of the 4 blue numbers are both ...
2
votes
2answers
51 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
2
votes
1answer
328 views

Proving the Chinese Remainder Theorem using the Pigeonhole Principle

I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle. The theorem that was provided: If n and m are relatively prime, then for all integers 0 ≤ a < n ...
2
votes
1answer
68 views

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color. This is a pigeon hole principle question and I have a ...
2
votes
1answer
89 views

Help with a pigeonhole principle?

Let $n \geq 1$ be an integer. Use the Pigeonhole Principle to prove that in any set of $n + 1$ integers from $\{1, 2, . . . , 2n\}$, there are two integers that are consecutive (i.e., di ffer by ...
2
votes
1answer
81 views

Small Combinatorical Question - Pigeonhole Principle Related

Suppose there are $77$ positive integers arranged in a row such that their sum is $140$. I want to show there is a sequence of adjacent integers in the row whose sum is $13$. My line of thought is ...
2
votes
1answer
105 views

pigeonhole principle with sequence of numbers

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$. ...
2
votes
1answer
120 views

Application of pigeonhole principle

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two. Clearly this is an application of the pigeonhole principle. However, I'm not ...
2
votes
1answer
192 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
2answers
144 views

Pigeonhole Question

This is an example from a Discrete math textbook: Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$. Answer: Here the pigeons constitute a $6$ ...
2
votes
1answer
200 views

A family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be linearly dependent

I was bored earlier and began to think of the pigeonhole principle, and it came to me that it could be used to show that a family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be ...
2
votes
2answers
324 views

Discrete Mathematics - Ice Cream random samples

How would you solve the following problem with Discrete Mathematics, and what is the answer? Suppose there are 5 different types of ice cream you like. How many random samples ice cream must be eaten ...
2
votes
2answers
397 views

Pigeonhole Principle Points in a Triangle

Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible ...