Questions involving the pigeonhole principle in Combinatorial Analysis.
39
votes
19answers
2k 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 ...
4
votes
2answers
437 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 ...
22
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 ...
4
votes
1answer
188 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 ...
8
votes
2answers
618 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. ...
3
votes
1answer
675 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 ...
0
votes
1answer
72 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 ...
54
votes
10answers
4k 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 ...
7
votes
4answers
335 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.
...
9
votes
2answers
1k 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 ...
5
votes
2answers
211 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!
0
votes
1answer
243 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 ...
6
votes
2answers
203 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 ...
6
votes
2answers
233 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 ...
3
votes
2answers
122 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
5answers
270 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 ...
2
votes
2answers
159 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 ...
