Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

55
votes
22answers
6k views

What is your favorite application of the Pigeonhole Principle?

The pigeonhole principle states that if $n$ items are put into $m$ "pigeonholes" with $n > m$, then at least one pigeonhole must contain more than one item. I'd like to see your favorite ...
5
votes
2answers
178 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 ...
8
votes
2answers
1k views

Chess Master Problem

From Introductory Combinatorics by Richard Brualdi We have a chess master. He has 11 weeks to prepare for a competition so he decides that he will practice everyday by playing at least 1 game a day. ...
5
votes
1answer
1k 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 ...
4
votes
2answers
1k 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 ...
37
votes
6answers
4k views

Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
24
votes
11answers
4k views

Prove that if two miles are run in 7:59 then one mile MUST be run under 4:00.

I'm in an argument with someone who claims that a two mile in 7:59 does not imply that one mile (at some point within the two miles) was covered in under 4:00. This is obviously wrong, but I'm not ...
11
votes
2answers
1k views

Pigeonhole principle Question: choose 100 numbers from 1~200,

Prove that if 100 numbers are chosen from the first 200 natural numbers and include a number less than 16, then one of them is divisible by another. How to prove this? many thanks....
24
votes
1answer
2k views

if there are 5 points on a sphere then 4 of them belong to a half-sphere.

If there are 5 points on the surface of a sphere then there is a closed half sphere containing at least 4 of them. It's in a pidgeonhole list of problems, but I think I have to use rotations in more ...
10
votes
3answers
803 views

A question related to Pigeonhole Principle

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of ...
8
votes
4answers
427 views

Prove that 2 students live exactly five houses apart if

There are 50 houses along one side of a street. A survey shows that 26 of these houses have students living in them. Prove that there are two students who live EXACTLY five houses apart on the street. ...
7
votes
2answers
480 views

Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other. Any help is appreciated!
4
votes
1answer
252 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 ...
1
vote
2answers
1k views

If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
3
votes
2answers
183 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$?
2
votes
1answer
140 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
1answer
155 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...
1
vote
2answers
304 views

For any arrangment of numbers 1 to 10 in a circle, there will always exist a pair of 3 adjacent numbers in the circle that sum up to 17 or more

I set out to solve the following question using the pigeonhole principle Regardless of how one arranges numbers $1$ to $10$ in a circle, there will always exist a pair of three adjacent numbers in ...
6
votes
2answers
467 views

A Pigeonhole Principle problem

101 positive integers are placed on a circle whose sum is 300.Prove that it is possible to choose from these numbers some consecutive numbers whose sum is equal to 200. (I don't know if the word ...
4
votes
2answers
1k 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$, ...
3
votes
2answers
190 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
3
votes
2answers
152 views

How are the pigeonholes calculated in this pigeon-hole problem?

The question is as follows: To prepare for a marathon, an elite runner runs at least once a day over the next 44 days, for a total of 70 runs in all. Show that there's a period of consecutive ...
2
votes
7answers
276 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
263 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 ...
1
vote
2answers
152 views

pigeonhole principle and division

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its ...
1
vote
2answers
884 views

Pigeonhole Principle question

There is a row of 35 chairs. Find the minimum number of chairs that must be occupied such that there are some consecutive set of 4 chairs or more occupied. I would like to have some hints as to ...
0
votes
2answers
79 views

Pigeonhole principle application

Say there are $p_{1}$ red balls and $p_{2}$ green balls. We put all the balls in a circle with $p_{1}+p_{2}$ places in total. It is forbidden that a ball (red or green) is placed between two red ...
63
votes
9answers
6k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
15
votes
6answers
541 views

Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
9
votes
1answer
264 views

Pigeonhole principle for a triangle

Consider a equilateral triangle of total area 1. Suppose 7 points are chosen inside. Show that some 3 points form a triangle of area $\leq\frac 14$.
4
votes
2answers
255 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 ...
10
votes
2answers
5k views

In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc ...
8
votes
1answer
616 views

Proof that Fibonacci Sequence modulo m is periodic? [duplicate]

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...
8
votes
3answers
354 views

Prove that the product of primes in some subset of $n+1$ integers is a perfect square.

I am trying to prove the following: The set $A$ consists of $n + 1$ positive integers, none of which have a prime divisor that is larger than the $n$th smallest prime number. Prove that there ...
7
votes
1answer
112 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
6
votes
1answer
98 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 ...
6
votes
5answers
3k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
5
votes
2answers
252 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!
4
votes
4answers
736 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 ...
3
votes
2answers
113 views

Polygon and Pigeon Hole Principle Question

Seven vertices are chosen in each of two congruent regular 16-gons. Prove that these polygons can be placed one atop another in such a way that at least four chosen vertices of one polygon coincide ...
3
votes
1answer
169 views

Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the ...
3
votes
2answers
141 views

Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
2
votes
3answers
271 views

Pigeonhole principle exercises

I have an exam in combinatorics on Friday and the pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions on this material? Thank you ...
1
vote
2answers
80 views

From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem. BdMO 2010 In a set of $131$ natural numbers, no number has a prime factor greater than 42. ...
0
votes
1answer
665 views

pigeonhole fun discrete math

How do i use the pigeon hole principle for these questions? A drawer contains 6 pairs of black, 5 pairs of white, 5 pairs of red, and 4 pairs of green socks. (a) How many single socks do we have to ...
9
votes
2answers
139 views

Smallest number of points on plane that guarantees an angle of at most $18^\circ$

What is the smallest number $n$, that in any arrangement of $n$ points on the plane, there are three of them making an angle of at most $18^\circ$? It is clear that $n>9$, since the vertices of a ...
7
votes
2answers
293 views

How to recognize a pigeonhole problem?

I'm going to split this into 2 questions, the first I think might have an answer, the second may not. First, is there a general way to recognize a pigeonhole problem as such? I mean are there some ...
6
votes
2answers
563 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
5
votes
4answers
350 views

The pigeonhole principle question

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- ...
5
votes
3answers
375 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. ...