Questions involving the pigeonhole principle in Combinatorial Analysis.
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 ...
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 ...
39
votes
1answer
578 views
A discrete math riddle
Here's a riddle that I've been struggling with for a while:
Let $A$ be a list of $n$ integers between 1 and $k$. Let $B$ be a list of $k$ integers between 1 and $n$. Prove that there's a non-empty ...
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 ...
11
votes
3answers
430 views
Arc sums for a circle of $k$ positive integers whose total sum is $n$
This problem got me thinking about the following more general scenario:
Suppose you have $k$ positive integers with total sum $n$, and you arrange them in a circle.
Given such an arrangement, you ...
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 ...
8
votes
2answers
619 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. ...
7
votes
4answers
337 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
280 views
Combinatorics proof
Suppose that $A$ is a set of 16 distinct natural numbers and that $1\leq p\leq100$ for every $p$ in $A $.
Prove that $A$ contains 4 different numbers $a$, $b$, $c$, and $d$, such that $a+b=c+d$.
7
votes
2answers
261 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....
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 ...
5
votes
2answers
212 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
1answer
141 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
4answers
194 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
125 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
182 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.
...
5
votes
1answer
99 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!
5
votes
2answers
106 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 ...
5
votes
0answers
112 views
How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?
This a shortened version (motivation from telecommunications stripped away) of a question I asked in MO in late May (no answers). I am mostly checking, if somebody has seen this or a related question ...
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 ...
4
votes
1answer
494 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
2answers
108 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
3answers
96 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) = ...
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 ...
3
votes
2answers
124 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
4answers
437 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
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 ...
3
votes
3answers
129 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, ...
3
votes
2answers
53 views
Pigeonhole Principle and Geometry
Consider any five points in the plane that have integer coordinates:
-Prove that there are two points such that the midpoint of the line segment joining those two points also has integer coordinates
3
votes
3answers
135 views
Proof using pigeonhole and greatest integer (floor) function.
The question is to prove that if m is a positive integer then,
$$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right] $$
for $x \in ...
3
votes
1answer
31 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
166 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 ...
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 ...
3
votes
1answer
101 views
pigeonhole principle 20 balls
I've worked out the answer to this as 13 since it's common sense, but we are supposed to apply the pigeon-hole principle, and I don't see how it is applicable here.
A bowl contains 10 red balls ...
3
votes
0answers
99 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
2answers
492 views
Subsets with equal sums
I have a problem to solve but I am in need of your help.
Subjects with equal sums:
Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), ...
2
votes
2answers
147 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
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 ...
2
votes
1answer
67 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
66 views
A game involving points in the integer plane - who wins?
I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of ...
2
votes
1answer
43 views
A family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be linearly dependent
I was bored earlier and began to think of the pigeonhole principle, and it came to me that it could be used to show that a family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be ...
2
votes
2answers
113 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
112 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 ...
2
votes
2answers
177 views
Pigeonhole Principle Points in a Triangle
Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible ...
2
votes
1answer
203 views
Pigeonhole principle to prove division
Here's a little question that we were shown in class:
Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$.
Prove that there are two elements of $A$ such that one is a ...
1
vote
4answers
59 views
Difference of two powers of $3$ divisible by $2011$
How to prove that there exists two powers of $3$ that differ by a number that is divisible by $2011$?
1
vote
2answers
152 views
Pigeonhole principle problem
The problem I'm working on says:
A basketball player has been training for 112 hours during 12 days. He has trained an integer number of hours every day. Prove that there was two consecutive days ...
1
vote
2answers
143 views
Bit strings (pigeonhole principle)
Here is how the question is posed:
Let $s_1$, $s_2$, $s_3, \ldots, s_{90}$ be 90 bit strings of length nine or less. Prove that there exist two strings $s_i$ and $s_j$ with $i \neq j$ that contain ...
1
vote
2answers
156 views
using pigeonhole principle for a hand of thirteen cards
Say I shuffle and deal a hand of thirteen cards. How can I apply the pigeonhole principle in these cases:
The hand has at least four cards in the same suit
The hand has at exactly four cards in some ...
