Questions involving the pigeonhole principle in Combinatorial Analysis.
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$, ...
4
votes
3answers
93 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) = ...
5
votes
3answers
124 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 ...
3
votes
1answer
30 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$ ...
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 ...
2
votes
1answer
63 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 ...
-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 ...
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.
2
votes
1answer
41 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 ...
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
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
...
3
votes
3answers
128 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, ...
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?
...
4
votes
2answers
107 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 ...
3
votes
1answer
97 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 ...
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 ...
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
5
votes
1answer
96 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!
2
votes
1answer
66 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...
39
votes
1answer
570 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 ...
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?
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 ...
6
votes
2answers
202 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 ...
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
...
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 ...
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.
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 ...
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
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 ...
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
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 ...
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 ...
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$, ...
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
...
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
...
0
votes
1answer
167 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
3answers
118 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 ...
5
votes
2answers
103 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 ...
2
votes
1answer
110 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 ...
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$.
5
votes
0answers
111 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 ...
7
votes
2answers
259 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....
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
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.
...
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
146 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 } ...
0
votes
1answer
242 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
0answers
241 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
vote
2answers
89 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 ...
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 ...
