Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

2
votes
1answer
82 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
71 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
0answers
71 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
98 views

Prove that there is an element in the given set having fractional part less than 0.01

Given a set $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},...\}$, prove that some of the elements have fractional part less than 0.01 when written in decimal form. Here is my attempt so far: Divide the range ...
2
votes
1answer
111 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
2answers
165 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
1answer
253 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
110 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
185 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
675 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
200 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
224 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
74 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
129 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
124 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
115 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
263 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
549 views

Maximum number of mutually orthogonal latin square pairs (definition provided)

An $n\times n$ matrix is defined to be a "latin square" if each row and column is a permutation of the first $n$ natural numbers. Two squares of same order are orthogonal if the $n^2$ pairs ...
1
vote
2answers
205 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
1answer
50 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
78 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
72 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
136 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
2answers
76 views

Candidates in an exam

443 candidates enter the exam hall. There are 20 rows of seats I'm the hall. Each row has 25 seats. At least how many rows have an equal number of candidates. My attempt Seat 25 in the first row 24 ...
1
vote
2answers
27 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
73 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
60 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
221 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
84 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
243 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 ...
1
vote
2answers
81 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 ...
1
vote
1answer
106 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?
1
vote
2answers
145 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 ...
1
vote
1answer
146 views

Constructive proof of pigeonhole principle

I'm trying to prove Pigeonhole principle with Coq proof assistant. Here is how I defined it: ...
1
vote
1answer
49 views

$[x-\frac{1}{n}, (n-1)x+\frac{1}{n}]$ contains an integer $\forall x\in \mathbb{R}$ and $\forall n\in \mathbb{N}$

For any real number x: Prove that among the numbers x,2x,...,(n-1)x ,there is one that differs from an integer by at most $\frac{1}{n}$. any hints for a pigeon solution. Non-pigeon solution ...
1
vote
1answer
93 views

In a class of 50 students, how many students are guaranteed to get the same score on an equally-weighted 20 question quiz?

I am completely lost... Any help is greatly appreciated. I am unsure where to go to better understand the concepts behind this problem. The problem: In a class of 50 students, how many students are ...
1
vote
1answer
43 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 ...
1
vote
1answer
69 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) ...
1
vote
3answers
106 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
3answers
109 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 ...
1
vote
1answer
136 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 ...
1
vote
2answers
96 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.
1
vote
2answers
76 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
1answer
351 views

Pigeonhole principle question

Suppose a graph with 12 vertices is colored with exactly 5 colors. By the pigeonhole principle, each color appears on at least two vertices. True or false? The correct answer is false, but I assumed ...
1
vote
2answers
73 views

Two hundred balls into one hundred boxes

We have distributed two hundred balls into one hundred boxes with the restrictions that no box got more than one hundred balls, and each box got at least one. Prove that it is possible to find some ...
1
vote
2answers
69 views

Pigeonhole principle question - relatively prime

Prove that every subset A of the set {2, 3, ... 99, 100} with |A| > 26, has at least one pair of integers that is not relatively prime. 2, 3, 5 .. , there are 26 primes below 100. Can someone give ...
1
vote
1answer
72 views

Choosing $2n-1$ points from $n\times n$ grid such that $3$ points always form a right triangle

NOTE: Looking for a hint,not the whole solution. BdMO 2012 Nationals Secondary Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always ...
1
vote
2answers
42 views

combinatorics - permutations question, possibly with pigeon hole

Let $A \in Mat_n(\mathbb R)$ such that $\forall i,j: a_{ij}\geq 0$ We are given: $$\forall j: \sum_{i=1}^n a_{ij}=\sum_{i=1}^n a_{ji}=1$$ show there's a permutation $\pi \in S_n$ such that $$\forall ...
1
vote
1answer
45 views

Composite Polynomials over UFDs

I was sitting in the Math room at my school and was reading the AMA Monthly and came across the proof for the following problem: Let $R$ be any UFD that is not a field. Suppose that $R$ has only ...