Questions involving the pigeonhole principle in Combinatorial Analysis.
1
vote
1answer
201 views
Pigeonhole principle and sequences problem
Could you please tell me if this is the right approach to tackle this problem.I translated it from Spanish into English, so please excuse the wording and let me know if there's something that is not ...
3
votes
3answers
134 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 ...
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 ...
53
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 ...
3
votes
1answer
165 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
486 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 ...
0
votes
2answers
294 views
Pigeonhole: 12 numbers between 10 to 100 - 2 have a difference divisible by 11
Prove that given 12 numbers between 10 to 100 - 2 have a difference divisible by 11.
I didn't understand the answer given in my lecture and thought that as usual I'd probably get a clearer answer ...
3
votes
1answer
670 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 ...
6
votes
2answers
232 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 ...
1
vote
1answer
32 views
Min Number of Values from {1,2,…,9} Such that diff of 2 picked values is 5
This is a question from Shcaum's whose answer I don't understand. Our textbook has 2 pages on the pigeonhole principle and I'm having quite a bit of difficulty with it.
Give the set ${1,2,...,9}$ ...
2
votes
2answers
480 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$), ...
0
votes
1answer
52 views
Possibility of constructing a desirable subset
Here is a question.I am quoting it:
Question by user Nahum Litvin Let A be a set of 100 natural numbers. prove that there is a set B
B⊆A
such that the sum of B's elements can be divided by ...
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!
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 ...
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 ...
4
votes
2answers
436 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 ...
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 ...
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 ...
3
votes
5answers
269 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
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 ...
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 ...
0
votes
1answer
113 views
Pigeonhole Principle used for Finding Numbers
I’m doing a review exercise that gives me the list of numbers from 100 to 1000.
I need to find the number of different numbers that have a 0.
I suppose I could do this with the Pigeonhole principle, ...
1
vote
2answers
281 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 ...
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 ...
7
votes
4answers
332 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.
...
3
votes
4answers
433 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 ...
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 ...
1
vote
2answers
189 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 ...
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. ...
1
vote
1answer
317 views
Pigeonhole principle question
Suppose a graph with 12 vertices is colored with exactly 5 colors. By the pigeonhole principle, each color appears on at least two vertices. True or false?
The correct answer is false, but I assumed ...
