Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

5
votes
2answers
81 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
385 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, ...
50
votes
21answers
4k views

What is your favorite application of the Pigeonhole Principle? [on hold]

The pigeonhole principle states that if $n$ items are put into $m$ "pigeonholes" with $n > m$, then at least one pigeonhole must contain more than one item. I'd like to see your favorite ...
1
vote
2answers
68 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
2answers
37 views

Pigeonhole principle on on proving cardinality of set [closed]

how to prove that any subset of the set {1,2,3,...26} of cardinality 14 or more must have two elements whose sum is 27
0
votes
0answers
27 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
49 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
62 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 ...
3
votes
1answer
113 views

Prove that there is an element in $ \{ \sqrt{3}, 2\sqrt{3}, 3\sqrt{3},…\}$ 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 ...
0
votes
0answers
36 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
64 views

Pigeonholing mod 4 points on plane.

I have the following problem as homework. Suppose there are 13 points in the plane, all with integer coordinates. Prove at least one quadrilateral with vertices on those points has a barycentre with ...
1
vote
2answers
69 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 ...
2
votes
1answer
81 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
2answers
98 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
898 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 ...
4
votes
1answer
263 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
1
vote
1answer
65 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 ...
0
votes
1answer
81 views

Prove if n<m there is at least one [(n/m)]?

Suppose there are n programmers in m cubicles. Prove that there must be at least one cubicle containing at least $\lceil \frac{n}{m} \rceil$ programmers. Note: I was not able to find the right sign [ ...
2
votes
7answers
240 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
43 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
375 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 ...
0
votes
2answers
77 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 ...
2
votes
0answers
30 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
1answer
19 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
86 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
59 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 ...
1
vote
3answers
409 views

Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another. Hint: Use the pigeonhole principle. I don't see how this ...
-1
votes
1answer
57 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
2
votes
1answer
98 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
116 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
vote
1answer
28 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
59 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 ...
1
vote
1answer
74 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
29 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 ...
-4
votes
2answers
53 views

Why when divided by 10 $a^2$ remainder can't equal 2,3 or 7?

Suppose $a \in Z$. Why when $a^2$ is divided by 10, the remainder can't equal 2,3 or 7 ?
11
votes
3answers
594 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 ...
0
votes
2answers
181 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
74 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
1answer
76 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. ...
1
vote
2answers
395 views

Pigeon Hole Principle Algorithm

The “pigeonhole principle” states that if n+1 objects (e.g., pigeons) are to be distributed into n holes then some hole must contain at least two objects. This observation is obvious but useful. ...
0
votes
3answers
117 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 ...
3
votes
1answer
83 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
1answer
53 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
85 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
69 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
78 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
59 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
62 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, ...
0
votes
0answers
56 views

Pigeon Hole Problem with coins

So, for this problem, I am told there is a jar containing: 13 pennies 12 nickels 9 dimes 8 quarters All of which are to be removed from the jar at random. So, ...
0
votes
1answer
428 views

Three exercises related to the pigeonhole principle

I got three questions while writing some exercises. Questions (1) Suppose S is a set of 6 positive integers, whose maximum is 14. Prove that the sums of elements in all non-empty subsets of S ...