Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

3
votes
3answers
147 views

How would you prove this theory of computation problem?

I have trouble proving the following statement, I'm supposed to do it for our theory of computation course but since I've been trying for days I'm looking for a hint : What is the smallest value ...
0
votes
2answers
84 views

Discrtete math proof by contradiction problem

I have the following problem that I must prove by CONTRADICTION: "Show that if you pick three socks from a drawer containing just blue socks and black socks, you must get either a pair of blue socks ...
0
votes
2answers
89 views

Pigeonhole Principle : $mn+1$ pigeons into $n$ holes.

If you have to put $n+1$ pigeons into $n$ holes, according to Pigeonhole principle, you will have to put two pigeons into the same hole. But what if you have to put $mn+1$ pigeons into $n$ holes? ...
0
votes
2answers
82 views

Pigeonhole principle application

Say there are $p_{1}$ red balls and $p_{2}$ green balls. We put all the balls in a circle with $p_{1}+p_{2}$ places in total. It is forbidden that a ball (red or green) is placed between two red ...
2
votes
0answers
59 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 ...
5
votes
2answers
243 views

Pigeonhole Principle and Sets

Can anyone point me in the right direction for this homework question? I know what the pigeonhole principle is but don't see how it helps :( Let $n\geqslant 1$ be an integer and consider the set S = ...
6
votes
2answers
574 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
1
vote
2answers
92 views

A problem about pigeonhole principle or graph.

Let $A=\{1,2,...,n\}$, where $\binom{n}{3}\geq n+1$. Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $A$ such that $\bigcup_{i=1}^{n+1}A_i=A$ and $n(A_i)=3$ for all $i$. How to prove or disprove that ...
0
votes
0answers
54 views

mantissa of pi and pigeonhole

It might be worth noting that this is a "pigeonhole principle" problem, but I'm not sure how to use PHP with it. The mantissa of pi is the fractional part of it (i.e. everything after the decimal ...
3
votes
2answers
101 views

Chessboard Pigeonhole Question

"Each square of a 4-by-19 chessboard is colored either green, yellow or red. Prove that the board must contain a rectangle consisting of at least four squares, and such that its four corner squares ...
2
votes
0answers
92 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 ...
0
votes
0answers
39 views

Pigeonhole Principle Party Question [duplicate]

I have this question in my assignment that I am not able to solve: In a conference where $n$ representatives attend, if $1$ of any $4$ of the attendants shake hands with the other $3$, prove that $1$ ...
1
vote
2answers
104 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
2answers
129 views

Pigeon Hole Question

Work shown below. "Suppose that the numbers 1 ,2 ,3 ,…,12 are randomly distributed around a circle. Prove or disprove each of the following assertions: a) There must be three neighbors whose sum is ...
7
votes
7answers
1k views

Are there rigorous formulation and proof of the pigeonhole principle?

The well known and intuitive pigeonhole principle states that if $n$ items are put in $m$ containers, and $n>m$, then there is at least one container which has more than one object. I've always ...
1
vote
1answer
77 views

Pigeon-Hole Problem

Let $p$ and $q$ be two positive integers so that the largest common divisor of $p$ and $q$ is 1. Prove that for any non-negative integers $s\leq p-1$ and $t\leq q-1$, there exists a non-negative ...
2
votes
7answers
279 views

How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
2
votes
2answers
105 views

Is this question a pigeon hole question?

How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15? Explain. It seems like this is similar to the birthday pigeon hole ...
4
votes
3answers
390 views

pidgeonhole problem need assistance

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013. This is a problem I had on an exam and I know that ...
2
votes
0answers
47 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)$ ...
0
votes
2answers
91 views

Need hint about with pigeonhole principle problem

$a_i$ and $b_i$ are two sequences with $2n$ elements where $\forall i:\ 1\leq i\leq 2n\implies\ 1 \leq a_i , b_i \leq n$ . I need to show that there are two subsets of indexes $I,J\subset [2n]$ so ...
0
votes
1answer
41 views

Solution Verification for How Many Class Rooms Are Needed

The Question There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed? My Work There ...
2
votes
2answers
91 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 ...
3
votes
1answer
186 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
2
votes
1answer
132 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 ...
0
votes
1answer
128 views

prove that the board contains a nontrivial rectangle whose 4 corner squares are all black or all red??

the question is, A 3 x 7 rectangle is divided into 21 squares each of which is coloured red or black. prove that the board contains a nontrivial rectangle (not 1 x k or k) whose 4 corner squares are ...
-1
votes
1answer
63 views

Pigeon Hole theory with 10 ints

If I have a set of 10 integers, is it possible to prove there are two that the difference is by a multiple of nine? My instinct says you can find two that differ by a multiple of 5 but not 9
1
vote
1answer
39 views

Factorial Divides Rising Power Proof Help

I'm trying to prove the following: $m^{\overline n} \equiv 0 \bmod n!$ Where $m^{\overline n} = m\left({m+1}\right)\left({m+2}\right)\ldots\left({m+n-1}\right)$, the product of $n$ successive ...
5
votes
0answers
61 views

Improving statement obtained by Pigeonhole principle

In this MSE question, this statement is proven: Room is cube-shaped, with side 3m. 136 flies fly in it. Prove that at any moment one can encompass 6 flies with a sphere of radius 90cm. Can ...
2
votes
1answer
89 views

Pigeonhole principle and room full of flies

Room is cube-shaped, with side 3m. 136 flies fly in it. Prove that at any moment one can encompass 6 flies with a sphere of radius 90cm. This is from a math class, I couldn't devise an ...
1
vote
1answer
81 views

Pidgeonhole Principle.

Suppose there are 3000 members in each of the club X, Y and Z. Each member from each of these three clubs has at least 3001 friends from the other two clubs altogether. Show that there are three ...
1
vote
2answers
39 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 ...
0
votes
3answers
533 views

Pigeon hole principle based puzzle question

A card-board box contains 12 pairs each of three different types of hand gloves used by batsman in cricket. They are separated into single units of gloves and all mixed. you can not see the gloves ...
1
vote
2answers
81 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 ...
0
votes
1answer
91 views

Proof of the pigeonhole principle by contradiction

I'm trying to prove this pigeonhole problem: Given that fact that $\lceil x \rceil < x + 1$, give a proof by contradiction that if $n$ items are placed in $m$ boxes then at least one box must ...
1
vote
1answer
82 views

Question about any 2 distinct primes and the difference between their multiples

I've been thinking about the following situation. Let $p$,$q$ be two distinct primes. Let $a,b \le pq$ be any two numbers such that $a \ge b$ where $p$ divides $a$ or $b$ and $q$ divides the other. ...
3
votes
1answer
134 views

Pigeonhole principle (I think): colored points in the plane

Suppose that each points in $\Bbb R^2$ is colored red, green or blue. Prove that either there are two points of the same color a distance $1$ unit apart, or there is an equilateral triangle of side ...
0
votes
3answers
123 views

Show that if taken 14 number from 1 to 25 at least one of them is multiple of another

Let $S = \{1, 2, \dots, 24, 25\}$. Show that for any subset $R \subset S$ with $|R| = 14$, there are $a,b \in R$ such that $a|b$. I know that it is a pigeonhole problem but i don't know how to solve ...
0
votes
1answer
63 views

Each Point in Cirlce

Each point in a circle is colored in one of 3 colors (blue, White, or red). Prove that one can find points that are vertices of an isosceles triangle, and either 3 points are all colored with the same ...
0
votes
1answer
98 views

Proof involving the Pigeonhole principle

Prove that among any given $n + 1$ positive integers, there are always two whose difference is divisible by $n$ My Answer: Using Pigeonhole principle: From a set of at least $2$ different $n+1$ ...
0
votes
1answer
96 views

Pigeon-hole principle applied to the game of tic tac toe

In a game of tic tac toe, noughts and crosses are drawn inside an unoccupied cell of a 3 x 3 matrix by two players I, II in alternating moves. Player I draws crosses and Player II draws noughts. The ...
0
votes
2answers
89 views

proving using pigeon hole principle

how would I prove this exercise: If we had five points in a square with sides of length one. How can we use the Pigeonhole Principle to prove that there are two of these points having distance at most ...
0
votes
1answer
159 views

Dividing a triangle into seventeen equal parts.

I was trying to solve a problem on Pigeonhole principle from Problem Solving Strategies by Arthur Engel. A target has the form of an equilateral triangle with side 2 units. If it is hit ...
0
votes
1answer
71 views

Pigeon Hole Problem with 3 integers

So, given any set of three integers, prove there is a pair whose sum us even, and then prove or disprove that there is a pair whose sum is odd. To prove that there is a pair whose sum is even, ...
3
votes
1answer
62 views

Qn on Pigeon-Hole Principle

Let S be a set of 10 positive integers ≤ 50. Show that there two different (but not necessarily disjoint) subsets of four integers such that the sums of the 4 integers in the sets are equal. Having ...
2
votes
0answers
79 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 ...
6
votes
2answers
861 views

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This is a difficult problem from competition training: Is there among first $100000001$ Fibonacci numbers one that ends with $0000$? Trainer suggests using pigeonhole principle.
0
votes
1answer
64 views

If 51 mosquitoes are sitting on a square with side 1m, are at least 3 of them within a disk of radius 1/7?

There are 51 mosquitoes on a square-shaped window with side 1 m. Can Stephen kill 3 mosquitoes with a circular plastic disk of radius 1/7 m in a single strike? I know this can be solved by ...
1
vote
2answers
171 views

Problem on pigeon hole principle

This is a problem based on pigeon hole principle. A tennis player has three weeks to prepare for a tennis tournament.She decides to play at least one set every day but not more than 36 in all.Show ...
-1
votes
2answers
89 views

Logic Questions with Pigeonhole Principle

"If $n$ objects are distributed into $k$ boxes, then at least one box must contain at least _____ objects." Fill in the blank How many people must we have in a room to ensure that six of them were ...