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
123 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
115 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
106 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 ...
2
votes
7answers
313 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
210 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
218 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
152 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
562 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
290 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
76 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
113 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
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
147 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
609 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
275 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
736 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
481 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
52 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
63 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
132 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
814 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
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
269 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
383 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
237 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
55 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
192 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
167 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
188 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
208 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
20 views

Half primes in the set

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
93 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
127 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
248 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
283 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
115 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
758 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
155 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
183 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
42 views

Proof related to pigeon hole principle to be done with induction

since the question is about a positive integer m, it's obvious that the use of mathematical induction needed, but to prove the fact for n = k+1 we have to use the pigeon hole principle, i am so ...
2
votes
1answer
85 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
99 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
176 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
52 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 ...