Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

1
vote
1answer
78 views

How many cards should be picked up?

In a standard deck of $52$ cards, what is the minimum number of cards you need to pick up, in order to guarantee that there is a suit with at least $3$ cards? Shouldn't I pick $10$ cards? Please ...
0
votes
1answer
86 views

Please let me know how to do this step by step. I had tried , but no solution yet…

A store has an introductory sale on 12 types of candy bars. A customer may choose one bar of any five different types and will be charged no more than $1.75. Show that although different choices may ...
3
votes
2answers
104 views

Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
1
vote
2answers
120 views

pigeonhole principle homework question

These are Homework question. They are pigeon hole principle questions and I have a very hard time with these unless I have worked on a similar problem before. Q.1. Prove that if we select 87 numbers ...
1
vote
3answers
171 views

Pigeonhole principle exercises

I have an exam in combinatorics on Friday and the pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions on this material? Thank you ...
4
votes
1answer
124 views

In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?
0
votes
2answers
56 views

Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Suppose you have a list of $n$ numbers, $n\geq 2$. Let $A$ be the set of differences of pairs of the $n$ numbers. Prove or disprove that at least one element of A must be divisible by $n-1$. Anyone ...
0
votes
1answer
82 views

Pigeonhole Principle Question…Fifteen different integers from 100 to 199 are given.

Question was too long to fit on title. Fifteen different integers from 100 to 199 are given. Show that it is always possible to select from these 15 integers at least two different sets $\{a_1, ...
3
votes
1answer
123 views

Lower bound for the number of coin weightings

The book that I am currently studying has the following exercise. Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by ...
9
votes
1answer
176 views

Pigeonhole principle for a triangle

Consider a equilateral triangle of total area 1. Suppose 7 points are chosen inside. Show that some 3 points form a triangle of area $\leq\frac 14$.
2
votes
1answer
118 views

An interesting problem using Pigeonhole principle

I saw this problem: Let $A \subset \{1,2,3,\cdots,2n\}$. Also, $|A|=n+1$. Show that There exist $a,b \in A$ with $a \neq b$ and $a$ and $b$ is coprime. I proved this one very easily by using pigeon ...
1
vote
3answers
95 views

Pigeonhole principle application sums and differences

Let $A \subset \{1,2,...,99\}$, prove or disprove the following: a. For $|A| = 27$ b. For $|A| = 26$ There are $2$ different numbers in $A$ that their sum or their difference can be divided with ...
1
vote
2answers
201 views

For any arrangment of numbers 1 to 10 in a circle, there will always exist a pair of 3 adjacent numbers in the circle that sum up to 17 or more

I set out to solve the following question using the pigeonhole principle Regardless of how one arranges numbers $1$ to $10$ in a circle, there will always exist a pair of three adjacent numbers in ...
2
votes
3answers
148 views

One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
0
votes
1answer
67 views

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart.

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart. My idea was place 25 girls in into pairs of rooms, and there is no scenario which ...
1
vote
4answers
103 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$?
0
votes
3answers
76 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 ...
1
vote
2answers
154 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
148 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
154 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 ...
1
vote
3answers
101 views

About the Pigeonhole principle

The principle says that: Let $k$ and $n$ be any two positive integers. If at least $kn+1$ objects are distributed among $n$ boxes, then one of the boxes must containat least $k+1$ objects. In ...
3
votes
1answer
101 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
410 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
59 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
43 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
110 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
50 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
145 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
208 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
89 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
109 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
79 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
250 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
94 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
412 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
200 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
190 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
80 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
87 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
338 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
122 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
1k 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?
3
votes
1answer
71 views

Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+ $. Prove that there exists a positive integer $n $ such that $k|n$ and the only digits in $n$ are 0's and 3's
11
votes
3answers
504 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
304 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 ...