Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

2
votes
0answers
44 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
88 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
33 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
90 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
150 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
126 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
126 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
60 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
36 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
86 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
79 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
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 ...
0
votes
2answers
252 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 ...
1
vote
1answer
80 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
114 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
119 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
62 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
95 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
84 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
86 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
96 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
66 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
58 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
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 ...
6
votes
2answers
850 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
63 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
155 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
86 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 ...
2
votes
1answer
253 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
0
votes
1answer
85 views

Pigeonhole proof of the existence of two numbers with given sum [duplicate]

Let $|W|=m+1$ and $W$ be a subset of $X=\{1,2,3,\dots ,2m\}$ ($m$ is any natural number). Prove there exists two numbers in $W$ whose sum is $2m+1$. Can anyone give me a hint to prove this? I ...
2
votes
2answers
85 views

Any two points inside a circle are within a diameter of each other.

In many problems involving the Pigeonhole Principle, we often assume the following lemma: Lemma: The distance between any two points in a circle of radius $r$ is at most $2r$. Intuitively, this ...
1
vote
2answers
78 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
268 views

Constructive proof of pigeonhole principle

I'm trying to prove Pigeonhole principle with Coq proof assistant. Here is how I defined it: ...
2
votes
2answers
88 views

Show that some 5 consecutive chairs must be occupied.

A group of 25 people are seated in a row of 30 chairs. Show that some 5 consecutive chairs must be occupied.
0
votes
4answers
204 views

How many subsets of $\{1, 2, …, n\}$ contain $1$ and how many don't? [closed]

Consider the set $A = \{1, 2, …, n\}$ (a) How many subsets of A contain $1$? I got $ 2^n - 2^{n-1}$ (b) How many subsets of A do not contain $1$? I got $2^{n-1}$ (c) Use the pigeonhole principle ...
0
votes
1answer
82 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 [ ...
0
votes
1answer
74 views

Number theoretical Application of the Pigeonhole Principle

I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle". ...
5
votes
1answer
64 views

On a strange pigeonhole principle problem

Given distinct integers $a_1, a_2, \cdots, a_{63}$. Prove that there exists $a_i, a_j, a_m, a_n$ such that $(a_i - a_j)(a_m - a_n)$ is divisible by $1984$. I have no idea of how to create the ...
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 ...
5
votes
4answers
685 views

General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
0
votes
3answers
51 views

123 persons in a cafe, and pigeons and boxes

$123$ persons are in a cafe. The sum of their ages is $3813$. Is it always possible to find $100$ among them so that their total age is greater or equal to $3100$? Looks like ...
0
votes
1answer
37 views

Regarding Thue's congruence theorem.

Did the mathematician Thue have a theorem where if $X\cdot N$ is congruent to $y \pmod m$, gcd$(y'm)=1$ then $1 \lt X \le \sqrt{m}$, or $1 \lt Y \le \sqrt{m}$? I'm not sure if I saw this in a number ...
4
votes
0answers
181 views

Select 100 integers from 1,2,…,200 [duplicate]

Prove that if 100 integers are chosen from 1,2,...,200, and one of the integers chosen is less than 16, then there are two chosen numbers such that one of them is divisible by the other. Thanks in ...
0
votes
0answers
44 views

four point in a row

We have painted all dots of page with two colors(blue and green), proof that there are four point with green color in a line that distance of any two neighbors of this four is one unit or there are ...
1
vote
1answer
38 views

Proving minimum exsistence of intersection cardinality

Let $F_1,F_2...F_{13}$ be sets such that $\forall 1\le i \le 13: F_i\subseteq [10]$ and $|F_i|=6$ when $[10]={1,2,3...10}$ prove that there are $1 \le j < k < l \le 13$ such that $|F_j \cap F_k ...
2
votes
2answers
87 views

Chords of a 20-gon

Twenty points lie on a circle, so as to form a regular polygon. Then they are split into ten pairs, and the points in each pair are connected by a chord. Prove that some pair of these chords have the ...
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 ...
0
votes
1answer
51 views

10 non-increasing or non-decreasing sequence from 101 random numbers [duplicate]

In $101$ random integer numbers $a[i],i=0, \cdots,100$, prove that we can always find $10$ non-increasing or non-decreasing sequence. A sequence is a sequence of numbers is an array of numbers ...