Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

9
votes
2answers
103 views

Smallest number of points on plane that guarantees an angle of at most $18^\circ$

What is the smallest number $n$, that in any arrangement of $n$ points on the plane, there are three of them making an angle of at most $18^\circ$? It is clear that $n>9$, since the vertices of a ...
3
votes
1answer
142 views

Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the ...
6
votes
5answers
3k views

Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
1
vote
1answer
104 views

Senators full of hatred [closed]

There are 51 senators in a senate. The senate needs to be divided into n committees such that each senator is on exactly one committee. Each senator hates exactly three other senators. (If ...
2
votes
1answer
113 views

Twenty distinct integers are chosen from {1,2,…,69} and their differences

Twenty distinct integers are chosen from {1,2,...,69}. Prove that amongst their pairwise differences there are at least four which are identical. I understand that the set {1...69} is ...
5
votes
1answer
53 views

Problem with $20$ integers less than $70$

20 pairwise distinct integers each less than 70 are taken and their pairwise differences are taken(magnitude of the difference). Show that there always exists 4 equal numbers. I somehow found ...
2
votes
1answer
31 views

$5$ points on a sphere [duplicate]

Diffuse $5$ points on a sphere. Prove there is a closed half-sphere that has at least $4$ points on it.
0
votes
1answer
61 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 ...
6
votes
2answers
804 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
0answers
48 views

combinatorics - pigeonhole principle - 2

I've advanced a little with this question but I'm not sure that I'm in the right direction. For any set $X$ with $n$ positive numbers, $n>5$, prove the existiance of subset $Y \subset X$ so that ...
12
votes
1answer
3k views

How many people would you need in a room to ensure with 100% probaility that three have the same birthday?

I am vaguely aware of the Pigeonhole principle and I understand that you would need 367 people to ensure that two people have the same birthday. I think that it may be required to have 734 people in a ...
15
votes
6answers
516 views

Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
2
votes
2answers
82 views

show that at least 3 balls have same weight

You are given 49 balls of colour red, black and white. It is known that, for any 5 balls of the same colour, there exist at least two among them possessing the same weight. The 49 balls are ...
-2
votes
1answer
40 views

PigeonHole Principle - Question [closed]

10 points are within a unit square. Prove there must be a pair of points with distance (from one another) is less than $0.48$
1
vote
1answer
61 views

Show that for any set of 201 positive integers less than 300, there must be two whose quotient is a power of three (with no remainder)

I guess we should not consider the zeroth power of 3 because it is equal to one. Any positive integer is a multiple of 1. Lets define the set S3 of integers that are multiples of 3 strictly less ...
1
vote
2answers
66 views

Pigeonhole principle: In every set of 100 integers, there exist two integers whose difference is a multiple of 37

What are the pigeons and the pigeonholes and how to prove this statements? At first I tried to the following: There are "100 choose 2" or 4950 pairs of integers. But I don't know how to move ...
-2
votes
1answer
63 views

Pigonhole Principle

Show that in any set of six classes, each meeting regularly once a week on a particular day of the week, there must be two that meet on the same day, assuming that no classes are held on weekends. Can ...
0
votes
3answers
52 views

Pigionhole Principle

Among any group of 3000 people there are at least 9 who have the same birthday. I cant figure out what's the object is and what's the box. And, how to apply it in the principle
0
votes
1answer
45 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 ...
1
vote
1answer
56 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 ...
0
votes
0answers
39 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 ...
0
votes
1answer
25 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
75 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 ...
4
votes
2answers
114 views

If ten points are on a unit square, one pair is at most $\sqrt2/3$ apart

Ten points are placed in a unit square. Show that there is a pair of points at most $\sqrt2/3$ apart. I'm not sure how to proceed with this problem, and have not had any luck so far.
1
vote
0answers
18 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
28 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. 
-2
votes
2answers
39 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.?
0
votes
2answers
60 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? ...
3
votes
3answers
133 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 ...
4
votes
2answers
1k views

Some three consecutive numbers sum to at least $32$

Here's a question we got for homework: We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$. I assume we need the ...
0
votes
0answers
30 views

How was the expression derived?

Prove that in any set of ten different two-digit numbers one can select two disjoint subsets such that the sum of numbers in each of the subsets is the same? (Reference, CRUX magazine March 1975). I ...
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 ...
0
votes
2answers
78 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
52 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 ...
4
votes
1answer
265 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 ...
6
votes
2answers
485 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, ...
5
votes
2answers
197 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 = ...
51
votes
21answers
5k views

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

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
87 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
42 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
78 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
74 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
114 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
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
66 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
91 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
85 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
111 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
978 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
73 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 ...