Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

3
votes
1answer
129 views

geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
1
vote
1answer
42 views

No. of functions satisfying a certain condition

This is from an old exam: Let $M$ be a set of functions from $\mathbb{Z}/3$ into itself. What is the least number of elements that $M$ must contain for there to surely be at least two elements ...
3
votes
1answer
77 views

Pigeonhole Proof

Let $n_1,n_2,\ldots,n_t$ be positive integers. Show that if $n_1+n_2+\cdots+n_t-t+1$ objects are placed into $t$ boxes, then for some $i$, $i = 1,2,\ldots,t$, the $i$th box contatins at least $n_i$ ...
0
votes
1answer
65 views

Pigeonhole Principle Help!!!

The nine entries of a $3 \times 3$ grid are filled with the integers -1, 1 and 0. Use the Pigeonhole Principle to prove among the eight resulting sums (three rows , three columns or two diagonals) ...
5
votes
1answer
149 views

Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?

I have recently came discovered Metamath. Supposedly the language is one that a computer may proof-check. I then began to look at concepts that I am familiar with, and decided to look up the pigeon ...
2
votes
1answer
56 views

Prove that there exists a numbered socket such that for every orientation, two equal numbers coincide

There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter ...
1
vote
2answers
68 views

Does the Pigeonhole principle apply in this problem?

I came accross this problem a while ago at school during a math contest. I dont remember the exact instruction (word for word) but it went something like : Randomed A and B, 2 natural integer $\in ...
4
votes
1answer
1k views

Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
2
votes
4answers
534 views

Pigeonhole principle: show that a class of nine has at least five male or five female students.

Here is the problem in full, start to finish, with no other special instructions or rules: "If there are 9 students in a class, show that at least 5 must be male or at least 5 must be female. Also, ...
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
93 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
112 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
122 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
183 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
125 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
59 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
84 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
180 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
127 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
99 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
212 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
104 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
156 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
150 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
157 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
102 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
103 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
416 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
61 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
69 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
111 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
153 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
218 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
113 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
78 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
256 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
431 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
204 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
194 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
88 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