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

5
votes
4answers
2k views

General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
5
votes
4answers
178 views

$x$ is equal to at least $51$ of $a_1,\frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$. Prove that $2$ of $a_1,\ldots,a_{100}$ are equal.

If $x$ is equal to at least $51$ number of the array $a_1, \frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$, prove that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal. That's ...
5
votes
4answers
413 views

Proving an interesting feature of any $1000$ different numbers chosen from $\{1, 2, \dots,1997\}$

Assume you choose $1000$ different numbers from the group $\{1, 2, \dots,1997\}$. Prove that within the $1000$ chosen numbers, there is a couple which sum is $1998$. I defined: pigeonholes: ...
5
votes
2answers
257 views

regarding Pigeonhole principle

Let A be a set of 100 natural numbers. prove that there is a set B $$B\subseteq A$$ such that the sum of B's elements can be divided by 100 I am stuck for a few days now. Please help!
5
votes
5answers
168 views

Pigeonhole principle problem involving inequality 0 < |$\sqrt{x} - \sqrt{y}$| < 1

21 integers are selected from {1, 2, 3, ..., 400}. Prove that two of them, say x and y, satisfy 0 < |$\sqrt{x} - \sqrt{y}$| < 1. I am confident you have to use and apply the Pigeon Hole ...
5
votes
1answer
260 views

Pigeon Hole Problem

Prove that of any 100 different twelve digit numbers (first digit cannot be zero) there are two of them with the same first and fifth digit. I'm new to this principle and need some assistance. I've ...
5
votes
1answer
208 views

In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?
5
votes
3answers
189 views

Pigeonhole Principle Problem combo inequality

Prove that for any subset of $\{1,2,3,...,300\}$ with $102$ elements, there exists elements $M$ and $x$ in that subset such that $100<M-x<200$. I think this is a pigeonhole problem, I wanna ...
5
votes
3answers
496 views

combinatorics: The pigeonhole principle

Assume that in every group of 9 people, there are 3 in the same height. Prove that in a group of 25 people there are 7 in the same height. I started by defining: pigeonhole- heights. pigeons-people....
5
votes
1answer
86 views

On a strange pigeonhole principle problem

Given distinct integers $a_1, a_2, \cdots, a_{63}$. Prove that there exists $a_i, a_j, a_m, a_n$ such that $(a_i - a_j)(a_m - a_n)$ is divisible by $1984$. I have no idea of how to create the ...
5
votes
2answers
256 views

Collection of numbers always in increasing or decreasing order

Anyone have any ideas on this question? I think you have to use the pigeon hole principle..but I am not sure about that? The numbers $1,2,3,\ldots,101$ are written down in a row in some order. Is ...
5
votes
1answer
5k views

Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
5
votes
1answer
130 views

Putnam Problem, Pigeonhole Principle

I have never attempted or considered any contest math problems, but I recently found a page of Putnam Prep problems in a recycling bin on campus and decided to give some a try since I am home for ...
5
votes
1answer
118 views

Problem with $20$ integers less than $70$

20 pairwise distinct integers each less than 70 are taken and their pairwise differences are taken(magnitude of the difference). Show that there always exists 4 equal numbers. I somehow found ...
5
votes
2answers
379 views

Pigeonhole Principle and Sets

Can anyone point me in the right direction for this homework question? I know what the pigeonhole principle is but don't see how it helps :( Let $n\geqslant 1$ be an integer and consider the set S = {...
5
votes
1answer
2k views

Combinatorics - pigeonhole principle question

This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition. An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a ...
5
votes
1answer
195 views

Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?

I have recently came discovered Metamath. Supposedly the language is one that a computer may proof-check. I then began to look at concepts that I am familiar with, and decided to look up the pigeon ...
5
votes
1answer
51 views

Application of Jacobi's Theorem in Box Principle

Today I was going through Problem Solving Strategies by Arthur Engel, and found this in the chapter Box Principle Before the question it says it "treats a theorem of Jacobi and its applications" ...
5
votes
0answers
61 views

Improving statement obtained by Pigeonhole principle

In this MSE question, this statement is proven: Room is cube-shaped, with side 3m. 136 flies fly in it. Prove that at any moment one can encompass 6 flies with a sphere of radius 90cm. Can ...
4
votes
2answers
2k views

Existance of multiple of $n$ with only 0 and 1 as it's digits [duplicate]

Possible Duplicate: Proof that a natural number multiplied by some integer results in a number with only one and zero as digits I read this somewhere recently: For any natural number $n$, ...
4
votes
2answers
2k views

Some three consecutive numbers sum to at least $32$

Here's a question we got for homework: We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$. I assume we need the ...
4
votes
4answers
999 views

Another pigeonhole principle question

Have another question for you today: A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at ...
4
votes
3answers
146 views

numbers from $1$ to $2046$

We have randomly taken $21$ integers from $1$ to $2046$. Show that we can take $a$, $b$ and $c$ from the previous $21$ integers in a way such that the following inequality holds \begin{equation} bc&...
4
votes
3answers
205 views

Pigeonhole Principle Homework Problem

Seven boys and five girls are seated (in an equally spaced fashion) around a circular table with 12 chairs. Prove that there are two boys sitting opposite one another. I used 'G' for girls and 'B' ...
4
votes
4answers
531 views

How to draw Square Diagonal? [duplicate]

Draw a 5x5 square. In 16 of 25 squares draw diagonals in such a way that no diagonal ends touch. How can I do this?
4
votes
1answer
291 views

discrete math about Pigeonhole Principle

Prove that any set of $10$ positive integers less than or equal to $100$ will always contain two subsets with the same sum. Can anyone help me with this problem? Thanks.
4
votes
3answers
400 views

pidgeonhole problem need assistance

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013. This is a problem I had on an exam and I know that ...
4
votes
1answer
180 views

Math and chess question!

Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?
4
votes
2answers
171 views

Minimum number of coins to ensure 10 coins of one type are selected

One coin is labelled with the number $1$, two different coins are labelled with the number $2$, three different coins are labelled with the number $3$, $\ldots$ , forty-nine different coins are ...
4
votes
5answers
512 views

The Pigeon Hole Principle and the Finite Subgroup Test

I am currently reading this document and am stuck on Theorem 3.3 on page 11: Let $H$ be a nonempty finite subset of a group $G$. Then $H$ is a subgroup of $G$ if $H$ is closed under the ...
4
votes
4answers
123 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers so ...
4
votes
1answer
2k views

Pigeonhole: Practical Applications in Computer Science

Most of the problems I've seen involving the pigeonhole principle have so far seemed fairly artificial. As I'm studying CompSci I'm interested what kind of practical, real world problems in CompSci ...
4
votes
3answers
269 views

Application of the pigeon hole principle

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows: "During a month with 30 days, a ...
4
votes
2answers
85 views

Pigeonhole principle on two coloured circle

Suppose a circle is divided into 200 congruent sectors, with 100 of them coloured red and the other 100 blue. A smaller concentric circle is placed on the larger circle and also so divided and ...
4
votes
2answers
299 views

Combinatorics Pigeonhole problem

Hello to all! So i have to do this problem: In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove ...
4
votes
2answers
341 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
4
votes
2answers
500 views

Prove two numbers of a set will evenly divide the other

We have a set A of numbers 1, 2, 3... to 200 The question is asking me to prove that if I choose 101 numbers from the set, there will be two such that one evenly divides the other. I know this ...
4
votes
3answers
195 views

proof using pigeonhole principle

I am struggling to come up with a proof to the following question(from cut-the-knot.org): Prove that if n is odd,then for any permutation $p$ of the set $\{1,2,3...,n\}$ the product $$P(p) = (1-p(1))(...
4
votes
1answer
268 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
4
votes
1answer
165 views

Students knowing others

There are 25 students in the class. It is known that among any three of them, two know each other. Show that there is a person who knows at least 12 other people. Thoughts: I know this is true since ...
4
votes
1answer
367 views

10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
4
votes
2answers
140 views

If ten points are on a unit square, one pair is at most $\sqrt2/3$ apart

Ten points are placed in a unit square. Show that there is a pair of points at most $\sqrt2/3$ apart. I'm not sure how to proceed with this problem, and have not had any luck so far.
4
votes
1answer
712 views

Divisibility and Pigeonhole principle

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq ...
4
votes
1answer
370 views

If any x points are elected out of a unit square, then some two of them are no farther than how many units apart?

If 5 points are randomly positioned in a unit square, no two points can be greater than square root of 2 divided by 2 apart; divide up the unit square into four squares, and, based on the pigeonhole ...
4
votes
1answer
80 views

Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
4
votes
3answers
85 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
4
votes
4answers
296 views

Pigeonhole principle (I think): colored points in the plane

Suppose that each points in $\Bbb R^2$ is colored red, green or blue. Prove that either there are two points of the same color a distance $1$ unit apart, or there is an equilateral triangle of side ...
4
votes
1answer
163 views

If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days

BdMO 2014 Nationals $X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates. I tried using the pigeonhole ...
4
votes
1answer
98 views

Elegant proof of icosohedron property

This problem was question A1 on the 2013 Putnam contest. Is there a better way to solve this problem than just using pigeonhole principle? Specifically, is there a group theoretic way to interpret ...
4
votes
1answer
266 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...