Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

3
votes
1answer
94 views

Pigeonhole proof of Rational Approximation Theorem

I am stuck with the solution to the following problem (it is also known as the Rational Approximation Theorem) at the Art of Problem Solving wiki, which states: Show that for any irrational $x \in ...
12
votes
6answers
395 views

Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
0
votes
1answer
57 views

Using The Pigeon-Hole Principle

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Here is the solution: Let $a,~a+1,...,a+n-1$ be the integers in the sequence. ...
3
votes
1answer
41 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
68 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
106 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
48 views

Average number of pigeon holes.

I'm an engineer not a mathematician, and I have a 3 part question that's applicable to a parallel computer system my team is designing. We have 10 CPU cores (ie - 10 pigeons) randomly reading from 10 ...
-2
votes
2answers
135 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 ...
4
votes
1answer
195 views

discrete math about Pigeonhole Principle

Prove that any set of $10$ positive integers less than or equal to $100$ will always contain two subsets with the same sum. Can anyone help me with this problem? Thanks.
0
votes
1answer
85 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
101 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
77 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
74 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 ...
2
votes
3answers
233 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
91 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? ...
9
votes
3answers
383 views

A question related to Pigeonhole Principle

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of ...
4
votes
2answers
190 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 ...
2
votes
1answer
180 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
77 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
82 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
313 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
117 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...
42
votes
1answer
905 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
91 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
496 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
276 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
129 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
306 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
86 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
251 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 ...
2
votes
1answer
365 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 ...
2
votes
2answers
102 views

Discrete Mathematics - Ice Cream random samples

How would you solve the following problem with Discrete Mathematics, and what is the answer? Suppose there are 5 different types of ice cream you like. How many random samples ice cream must be eaten ...
1
vote
1answer
37 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
2answers
126 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
88 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
207 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
381 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
134 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
2answers
61 views

graph-theory combinatorics

Here is a combinatorics problem having to do with graph-theory Ten players participate at a chess tournament. Eleven games have already been played. Prove that there is a player who has played at ...
1
vote
3answers
247 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
330 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 ...
1
vote
3answers
163 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 ...
7
votes
3answers
244 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 ...
3
votes
1answer
271 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 ...
5
votes
5answers
1k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
7
votes
2answers
306 views

Combinatorics proof (any set of 16 numbers from 1 to 100 contains repeated sums)

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
185 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 ...
9
votes
2answers
603 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....
1
vote
1answer
104 views

Pigeon principle question: Nine points in a diamond

A diamond (a parallelogram with equal sides) is given, and its sides are 2 cm long. The sharp angels are 60 degrees. If there are nine points inside the diamond, prove that there must be two of them ...
5
votes
4answers
261 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- ...