Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

2
votes
1answer
70 views

Small Combinatorical Question - Pigeonhole Principle Related

Suppose there are $77$ positive integers arranged in a row such that their sum is $140$. I want to show there is a sequence of adjacent integers in the row whose sum is $13$. My line of thought is ...
2
votes
1answer
98 views

pigeonhole principle with sequence of numbers

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$. ...
2
votes
1answer
95 views

Application of pigeonhole principle

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two. Clearly this is an application of the pigeonhole principle. However, I'm not ...
2
votes
1answer
135 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
2answers
126 views

Pigeonhole Question

This is an example from a Discrete math textbook: Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$. Answer: Here the pigeons constitute a $6$ ...
2
votes
1answer
238 views

Probability problem- Are there atleast 3 balls with same colour radius and in same box?

The question is as follows, it came in RMO in 1990. It most likely involves probability..as far I think. Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, ...
2
votes
1answer
127 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
130 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 ...
2
votes
2answers
191 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 ...
2
votes
2answers
355 views

Pigeonhole Principle Points in a Triangle

Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible ...
2
votes
1answer
280 views

Pigeonhole principle to prove division

Here's a little question that we were shown in class: Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$. Prove that there are two elements of $A$ such that one is a ...
2
votes
2answers
133 views

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n ...
2
votes
2answers
82 views

A question about the Pigeonhole Principle and linear equations over $\mathbb{Z}$

This may be a bit trivial (apologies if it is), but I was wondering if there was an elementary way to compute the cardinality of the solution set in the following situation: How many solutions would ...
2
votes
1answer
206 views

pigeonhole principle related problem

I'm given the problem: In a tournament which 18 teams participate, a team being matched with another in a round don’t match again in the follwoing (later) rounds. After 8 rounds prove that there are 3 ...
2
votes
1answer
52 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
1answer
254 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 ...
2
votes
0answers
52 views

Using the pigeonhole principle to prove there is at least a sum of numbers bigger than 29.

There is a circumference with 14 points $\{p_{1}, p_{2}, ... p_{14}\}$. These points are assigned numbers 1 to 14 randomly. It must be proven that if points are taken three-by-three, these triplets ...
2
votes
0answers
74 views

Seeking Feedback on my solution: Maximum area of a triangle inside a rectangle.

I was solving problem 3.3.16 from Paul Zeitz's book "The Art and Craft of Problem Solving." The problem reads Inside a 1 x 1 square, 101 points are placed.Show that some three of them form a ...
2
votes
0answers
36 views

Need a hint with permutations and pigeonhole-principle question

let $\pi_1,\pi_2,\pi_3\in S_{28}$. Help me prove that there are two sub-sequences of 28 with length 4 $i_1< i_2 <i_3<i_4,\ and\ \ j_1<j_2<j_3<j_4$ so that $\pi_q(i_n)=\pi_p(j_n)$ ...
2
votes
1answer
120 views

A Pigeonhole Principle Question

Show that in a party of $n$ people, there are two people having identical number of friends. I am a beginner at Pigeonhole Principle problems and have produced a solution to this intermediate level ...
2
votes
0answers
76 views

2014 points inside a cube

$2014$ points are chosen inside a cube with side $13$. Can a cube with side $1$ be found inside it so that it doesn't contain any of chosen points? This must be a problem solved using ...
2
votes
2answers
89 views

Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
2
votes
0answers
75 views

How to estimate pigeonhole principle?

I was thinking about this after my professor mentioned the pigeonhole principle in class. Let's say we have $N$ items and $M$ containers. Here we assume $N > M$. We will randomly place each of the ...
2
votes
1answer
185 views

With the pigeon hole principle how do you tell which are the pigeons and which are the holes?

For example, I was reading this example from my textbook: Let S be a set of six positive integers who maximum is at most 14. Show that the sums of the elements in all the nonempty subsets of S ...
2
votes
3answers
250 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 ...
2
votes
1answer
261 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 ...
1
vote
4answers
137 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$?
1
vote
3answers
197 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 ...
1
vote
2answers
753 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 ...
1
vote
2answers
207 views

Pigeonhole principle problem

The problem I'm working on says: A basketball player has been training for 112 hours during 12 days. He has trained an integer number of hours every day. Prove that there was two consecutive days ...
1
vote
3answers
345 views

Show that for any subset of $10$ distinct integers there exists two disjoint subsets equal in sum

The title abbreviates the following homework exercise on the Pigeonhole Principle. Show that for any set of $10$ distinct integers from $1 \dots 60$ there exists two disjoint subsets of equal ...
1
vote
1answer
82 views

using the pigeon hole principle to prove that some integer with a sequence of ones and zeros is divisible by some d

Let $d$ be any fixed natural number. Show that there must exist an integer of the form $11\ldots1100\ldots 00$ (that is a integer whose digits consist of a sequence of $1$'s followed by $0$'s) which ...
1
vote
3answers
131 views

Proof Involving Pigeonhole Principle

Let $a_1, a_2, ..., a_n$ be positive integers all of whose prime divisors are $\le$ 13. a) Show that if $n \ge 65$ then there exist two of these integers whose product is a perfect square. [DONE] b) ...
1
vote
2answers
130 views

Pigeonhole Principle Proof

2004 flies are inside a cube of side 1. Show that some 3 of them are within a sphere of radius 1/11. I am not sure how to begin the proof especially since we are asked to work on a sphere rather than ...
1
vote
1answer
119 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 ...
1
vote
2answers
271 views

Bit strings (pigeonhole principle)

Here is how the question is posed: Let $s_1$, $s_2$, $s_3, \ldots, s_{90}$ be 90 bit strings of length nine or less. Prove that there exist two strings $s_i$ and $s_j$ with $i \neq j$ that contain ...
1
vote
2answers
209 views

using pigeonhole principle for a hand of thirteen cards

Say I shuffle and deal a hand of thirteen cards. How can I apply the pigeonhole principle in these cases: The hand has at least four cards in the same suit The hand has at exactly four cards in some ...
1
vote
2answers
91 views

Pigeon-hole with the sum of 3 numbers

In any set consisting of exactly 7 different numbers chosen from the first 9 positive whole numbers, there are always 3 different numbers whose sum is 15. Is this true or false? There's a follow-up ...
1
vote
1answer
54 views

Show there exists a sequence of days within $49$ days where exactly $20$ hrs. are worked

Assume an integer number of hours will be worked each day for $49$ consecutive days. Further assume that at least $ 1 \frac{\text{hrs}}{\text{day}}$ and at most $11 \frac{\text{hrs}}{\text{wk}}$ can ...
1
vote
1answer
84 views

pigeonhole question with sets and sum of numbers

This question is meant to be solved with pigeonhole principle. But I can't solve it. I just can't figure out what is the pigeon and what is the pigeon hole. I don't really have a clear direction. ...
1
vote
1answer
80 views

Solve using Pigeonhole principle

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44. How can I prove this using pigeonhole ...
1
vote
2answers
145 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
1answer
61 views

Show that for any set of 201 positive integers less than 300, there must be two whose quotient is a power of three (with no remainder)

I guess we should not consider the zeroth power of 3 because it is equal to one. Any positive integer is a multiple of 1. Lets define the set S3 of integers that are multiples of 3 strictly less ...
1
vote
2answers
35 views

Minimum number of students, where 100 students from the same state go to the same university

I was given the following question: I thought of the problem like this. Each of the $50$ states represents a box, and I want $100$ people in the same box. By the pigeon-hole principle, we are ...
1
vote
2answers
75 views

From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem. BdMO 2010 In a set of $131$ natural numbers, no number has a prime factor greater than 42. ...
1
vote
2answers
63 views

Pigeon Hole Principle on a set of n elements

Homework question: It is asking us to prove that if we have $\frac{n}{2} + 1$ integers selected from a set$ A = {1, 2, ..., n}$, $n$ being an even integer, then the selection includes integers $x$ ...
1
vote
2answers
1k views

If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
1
vote
2answers
229 views

Prove a number is even using the Pigeonhole Principle

Let n be an odd integer and let f be an [n]-permutation of length n, where [n] is the set of integers 1, 2, 3,...n Show that the number ...
1
vote
1answer
86 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 ...
1
vote
2answers
273 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 ...