Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

2
votes
1answer
55 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
102 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
39 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
22 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
53 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
60 views

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
57 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
23 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 ...
-2
votes
2answers
43 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 ?
0
votes
0answers
31 views

How to solve Pigeon hole principle problems with multiple objects

I understand how to use this principle given 2 parameters such as 8 cats and 4 litterboxes will have at least one box with 2 cats in it. However, a question like this stumps me: Dave's ...
0
votes
2answers
133 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
65 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
65 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
68 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
109 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
52 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
75 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
59 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
67 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
48 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
52 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
45 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, ...
3
votes
1answer
40 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
66 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 ...
5
votes
2answers
738 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 says use pigeonhole principle. I do not know how.
0
votes
1answer
54 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
105 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
78 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
241 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
77 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
74 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
67 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
123 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
79 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
173 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
0answers
57 views

Elementary Pigeonhole Principle Question

Is my reasoning here correct? If not, advice would be appreciated. Thank you for your time! We assume that $A$ is finite and $f: A \rightarrow A$. We show that $f$ is one-to-one iff $ran \ f = A$. ...
0
votes
1answer
71 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
57 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 ...
1
vote
1answer
64 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 ...
6
votes
3answers
547 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
48 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
29 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
163 views

Select 100 integers from 1,2,…,200

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
42 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 ...
0
votes
0answers
38 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
1
vote
1answer
34 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
80 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
123 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
33 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 ...
1
vote
1answer
99 views

Combinatorics pigeonhole principle question.

There are $n$ people at a meeting, each of whom chooses $3$ distinct numbers between $1$ and $11.$ $\quad({\sf a})$ What is the smallest value of $n$ which guarantees that at least two people choose ...