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

3
votes
1answer
98 views

Qn on Pigeon-Hole Principle

Let S be a set of 10 positive integers ≤ 50. Show that there two different (but not necessarily disjoint) subsets of four integers such that the sums of the 4 integers in the sets are equal. Having ...
3
votes
1answer
163 views

Pigeonhole principle problem involving circle and its chords

Several chords are drawn in a circle of radius 1 such that each diameter intersects no more than 4 of them. Prove that the sum of their lengths does not exceed 13.
3
votes
1answer
87 views

Prove that for positive number, some multiple only has 0 and d as it's digits

Let $ n$ be a positive integer, and let $1<=d<=9$. Show that some multiple of $n$ has $0$ and $d$ as its only digits. I don't know how to even start this question. It's under the pigeonhole ...
3
votes
2answers
251 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
3
votes
1answer
75 views

Prove that there exists a numbered socket such that for every orientation, two equal numbers coincide

There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter ...
3
votes
1answer
64 views

Smallest subset of $\{1,2,…,4n\}$ with a certain property

Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$. Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
3
votes
1answer
41 views

7 points on a closed disk, one must be the center

I am trying a pigeonhole strategy for proving this assertion of a MO test: "Given 7 points on a closed disk of radius 1 such that the distance between any two of this points is at least one, then one ...
3
votes
2answers
120 views

Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
3
votes
1answer
144 views

Pigeonhole proof of Rational Approximation Theorem

I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states: Show that for any irrational $x \in ...
3
votes
1answer
52 views

Pigeonhole Principle - permutations

You are given three permutations of $\langle 1,\dotsc, 28 \rangle$. Show that two of them have common sub-sequence of length four. I tried saying that every permutation has $\binom{28}{4}$ ...
3
votes
0answers
31 views

Show that if you paint 6 dots on the unit square, then there is always a couple of 2 points with distance <=2/3 [duplicate]

This question is difficult for me. Anyone knows how to divide the unit square by using pigeonhole principle?
3
votes
0answers
38 views

Markov's Inequality and the Pigeonhole Principle

I heard someone in my department claim that Markov's inequality was just a continuous version of the pigeonhole principle. It seemed reasonable, but I'm struggling to make their connection precise. ...
3
votes
1answer
139 views

Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or ...
3
votes
1answer
65 views

let $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b \in A$ such that $n \leq a-b \leq 2n$

I'm having difficulties solving this question and would appreciate a nudge in the right direction. I think this is best solved with pigeonhole, but what are the pigeons and what are the holes?
3
votes
1answer
124 views

Prove that there is an element in $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},…\}$ having fractional part less than 0.01

Given a set $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},...\}$, prove that some of the elements have fractional part less than 0.01 when written in decimal form. Here is my attempt so far: Divide the range $...
3
votes
1answer
116 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
3
votes
0answers
108 views

Milk bottles and pigeonhole. [duplicate]

Possible Duplicate: Chess Master Problem A child drinks at least 1 bottle of milk a day. Given that he has drunk 700 bottles of milk in a year of 365 days, prove that for he has drunk exactly ...
2
votes
7answers
320 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
2
votes
1answer
225 views

geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
2
votes
3answers
220 views

A pigeonhole problem from “Conjecture and Proof”

I don't really know how to start this problem at all. I would like a solution or even hints. "Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$" The chapter in ...
2
votes
3answers
153 views

One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
2
votes
3answers
570 views

Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.

Choose any 38 different natural numbers less than 1000. Prove that among the selected numbers there exists at least two whose difference is at most 26. I think I need to use pigeon hole principle, ...
2
votes
2answers
301 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
3answers
85 views

Placing Pandas in a Triangle Pen

I am working on a bit of a silly problem in my introductory discrete mathematics course. I have five pandas that I need to place in a pen, and I have a pen that is the shape of an equilateral triangle ...
2
votes
2answers
124 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 week....
2
votes
2answers
104 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
151 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
623 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
279 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
755 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 $(x_{ij},...
2
votes
2answers
492 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
2answers
51 views

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$. My approach: Let $a_1,a_2,a_3,\ldots,a_{2^{n+1}-1}$ ...
2
votes
1answer
53 views

How can we prove that every sequence of $30$ elements from a set of three repeats a subsequence of length 3?

How can we prove that for every series over $30$ elements(included $30$), there must be a "sub" three element series then will repeat itself? (Series's numbers are only $\{1,2,3\}$) Example for a "...
2
votes
3answers
60 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
69 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
158 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
865 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 two ...
2
votes
1answer
1k 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
277 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
411 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
243 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
1answer
56 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
95 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
204 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
170 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
203 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
217 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 arbitrary. ...
2
votes
1answer
29 views

Half primes in the set [closed]

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
2
votes
1answer
113 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 ...