Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then one at least one container has more than one item.

learn more… | top users | synonyms

0
votes
1answer
56 views

Whether it is the pigeonhole principle?

I had a question, and I am just wondering if it is a question that involves combinations/permutations or the pigeonhole principle. In a class are $20$ students. What is the probability that at least ...
2
votes
1answer
72 views

Pigeon hole principle

Out of eleven square integers we can pick six integers such that $a^2+b^2+c^2=d^2+e^2+f^2 \,(\mod 12)$ This was probably the toughest question in section b of our maths paper.I knew this question ...
1
vote
0answers
85 views

Prove that $ax^2 + by^2 \equiv c \ ( \mod{p})$ has integer solutions

Let $p$ be a prime number and $a, b, c$ integers such that $a$ and $b$ are not divisible by $p$. Prove that $ax^2 + by^2 \equiv c \ ( \mod{p})$ has integer solutions Well, this problem can be ...
1
vote
1answer
52 views

Square labeled with same number.

Recently I met this combinatorics problem: "Let all points with integer coordinates in a plane be labeled with one of the numbers $1,2,3,...,n$. Prove that there is a rectangle whose vertices are ...
0
votes
1answer
92 views

Pigeonhole question about distinct sums

How do I show with the pigeonhole principle that no seven positive integers not exceeding $24$ can have sums of all subsets different. As observed by Ross Millikan, the simplest possible approach ...
1
vote
0answers
21 views

Pigeon hole principle:Trominoes and chessboards

Heres the question: What is the largest number of squares on an 8 $\times$8 checkerboard which can be colored green,so that in any one arrangement of three squares ("tromino"),at least one square ...
1
vote
0answers
31 views

Hard pigeonhole principle problem. [duplicate]

Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7. 
-1
votes
2answers
99 views

prove that every lossless compression algorithm must result in increasing the file size for some inputs.? [closed]

Using Pigeonhole Principle prove that every lossless compression algorithm must result in increasing the file size for some inputs.?
3
votes
3answers
186 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
549 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
197 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
88 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
69 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
372 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 = ...
7
votes
2answers
892 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, ...
2
votes
2answers
104 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
72 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
149 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
130 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
143 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
177 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 ...
8
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
82 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
314 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
264 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
398 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
61 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
93 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
132 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
95 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
678 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
179 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
272 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
64 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
47 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 ...
3
votes
1answer
95 views

Pigeonhole principle and room full of flies

Room is cube-shaped, with side lengths $3$ meters. $136$ flies flies are in it. Prove that: At any moment you can encompass $6$ flies with a sphere of radius $90$ centimeters. This is ...
1
vote
1answer
84 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
78 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
723 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
139 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
324 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
85 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. ...
4
votes
4answers
276 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
144 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
66 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
110 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
142 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
97 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 ...