Questions involving the pigeonhole principle in Combinatorial Analysis.
1
vote
2answers
190 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 ...
1
vote
2answers
42 views
how to apply hint to question involving the pigeonhole principle
The following question is from cut-the-knot.org's page on the pigeonhole principle
Question
Prove that however one selects 55 integers $1 \le x_1 < x_2 < x_3 < ... < x_{55} \le 100$, ...
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 ...
1
vote
2answers
48 views
Counting Subset Properties
Let $N=\{1,2,...,100\}$ and $A$ be a subset of $N$ with $|A|=55$. Show that $A$ contains two numbers with difference $9$. Is this also true for $|A|=54$?
I was trying to solve this via the pigeonhole ...
1
vote
1answer
63 views
Twenty distinct integers are chosen from {1,2,…,69}. Prove that amongst their pairwise differences there are at least four which are identical.
I understand that the set {1...69} is arbitrary. I'm having a hard time proving it. Should I prove through induction or use the pigeon hole principle?
1
vote
1answer
81 views
Pigeonhole problem
I'm struggling with this problem for a while now, and I just can't figure it out.
Prove: Let $n_1, n_2, . . . , n_t \in \mathbb{N}^+$
If $n_1 + n_2 + . . . + n_t-t + 1$ Objects are laid in t
...
1
vote
2answers
78 views
Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$.Prove that multiplication two number of these numbers are complete square
Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$ is formed.
Prove that multiplication two number of these numbers are complete square.
Thank you.
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 ...
1
vote
1answer
52 views
birthday problem help
For the birthday problem, how many people are needed to ensure that at least three people are born in the same month?
After looking at the problem I think the answer would be 25 because
12 + 12 + 1?
...
1
vote
1answer
145 views
Pigeonhole Principle on Graphs
I just have a last minute question for my combinatorics final (which is in one hour!!).
My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole ...
1
vote
3answers
127 views
Pigeon hole birthday problem?
If there are 10,000 people, how many people must have the same birthday (ignoring year)?
This is the way I went about this problem:
10000 people / 365 days in a year = 27.397 people per day
...
1
vote
2answers
90 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 ...
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}$ ...
1
vote
1answer
31 views
pigeonhole problem understanding a step
I've got $\sum_{i} F_+(i) \ge k \sum_{i} G(i)$ and it says that implies there's an $i$ such that $F(i) \ge k G(i)$, $F_+$ is the positive part of $F$ and $\sum_{i} F(i) = 0$. How does it follow?
From ...
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 ...
0
votes
1answer
66 views
How do I show this, possibly using the pigeonhole principle?
Show that if you choose any $12$ real numbers between $1$ and $12$, three of them must be the sides of an acute triangle.
0
votes
3answers
119 views
How to apply pigeonhole principle to this problem?
There are 33 students in the class and sum of their ages 430 years. Is it true that one can find 20 students in the class such that sum of their ages greater 260 ?
My approach:
The average age of ...
0
votes
4answers
286 views
Can you help me solve these questions related to a Logical theory?
In a group of 200 people, number of people having at least primary education (assuming - Category I): number of people having at least middle school education (Category II): number of people having ...
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 ...
0
votes
2answers
299 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 ...
0
votes
1answer
114 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, ...
0
votes
1answer
125 views
Using the pigeonhole principle to prove there is at least two groups of people whose age sums are the same.
In a room there are 10 people, none of whom are older than 100 (ages are given in whole numbers only) but each of whom is at least 1 year old. Prove that one can always find two groups of people ...
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 ...
0
votes
1answer
60 views
Combinatorics pigeonhole probems
Let there be $R$ red and $B$ blue balls, with each ball distinct from the other (even of the same colour). $M$ balls ($(1)$ assume $M<R,B$) are to be chosen. What is the probability that the number ...
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 ...
0
votes
3answers
48 views
Pigeon holes principle
Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
0
votes
1answer
50 views
Ramsey's theory inequality with $t$-subsets
Let $q_{1},\, q_{2}, \ldots, q_{k},t$ be positive integers, where $q_{1}\geq t, q_{2}\geq t, \ldots, q_{k}\geq t$. Let $m$ be the largest of $q_{1},q_{2}, \ldots, q_{k}$.
Show that
...
0
votes
1answer
168 views
Three exercises related to the pigeonhole principle
I got three questions while writing some exercises.
Questions
(1) Suppose S is a set of 6 positive integers, whose maximum is 14. Prove that the sums of elements in all non-empty subsets of S ...
0
votes
1answer
52 views
Consider a set A of 100, 000 arbitrary integers. Prove that there is some subset of 22 integers that end in the same last three digits.
Consider a set A of 100, 000 arbitrary integers. Prove that there is
some subset of 22 integers that end in the same last three digits.
I'm new to this principle and need help on this problem.
0
votes
1answer
52 views
Another version of PP
Prove the following version of the pigeonhole principle. Let $m$ and $n$ be
positive integers. If $m$ objects are distributed in some way among $n$ containers,
then at least one container must hold at ...
0
votes
0answers
243 views
PigeonHole Principle how to apply this?
This problem was suggested to me by one of the students. Imagine you are one
of four players. Each player gets two cards from a regular deck of cards. Your
hand is 10 10. You lose only if some other ...
-1
votes
2answers
52 views
Pigeonhole Principle
Explain the following using Pigeonhole Principle is it is true:
1) If we choose 10 points in a $3 x 3$ inch square, there must be two points of the 10 which are at distance less than or equal to ...
