Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

-5
votes
2answers
49 views

Discrete mathematics: Question regarding “Pigeonhole principle”. [closed]

Each point in the plane is coloured either red or blue. Show that there are two points of the same colour which are exactly 1 cm apart.
10
votes
2answers
1k views

Pigeonhole principle: Five points on an orange

Five points are drawn on the surface of an orange. Prove that it is possible to cut the orange in half in such a way that at least four of the points are on the same hemisphere. (Any points lying ...
3
votes
4answers
97 views

Application of Pigeon-Hole Principle to balls in bins.

Given $n$ balls placed in $m$ boxes, prove that if $n < \frac{m(m-1)}{2}$ then at least two boxes have same number of balls in them.
3
votes
1answer
48 views

Proof that only a certain amount of points can fit in a rectangle

Prove that no more than 8 points can fit in a rectangle with sides d and 2d if any 2 points have to be at least d units away from each other. I have proved that no more than 6 points can fit ...
1
vote
3answers
88 views

Pigeonhole principle 3

I need help on this question, I'm lost and really don't know how to proceed: Use the pigeonhole principle to prove that in a round-robin chess tournament (with 18 participants) there will be at least ...
3
votes
1answer
68 views

Choose 8 distinct integers from $\{1, 2,\dots,16,17\}$. Show that the eight contain at least three pairs with a common difference for _any_ choice.

This problem is from the 1999 Canada National Olympiad. I am stuck trying to prove the first part using the pigeonhole principle. Is there a refinement that will allow it to be used more sharply, or ...
1
vote
1answer
32 views

Problem involving weights of blocks and pigeonhole principle

So I have been trying to solve the following problem: Suppose you are given n blocks, each of which weighs an integral number of pounds, but less than n pounds. Suppose also that the total weight of ...
6
votes
2answers
576 views

Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is ...
0
votes
2answers
60 views

problem related to pigeon hole principle

please help me to solve this using pigeon hole principle Suppose that S is a set of n integers. Show that one can choose a nonempty subset T of S such that the sum of all elements of T is divisible ...
-1
votes
1answer
47 views

Discrete matematics, using pigeonhole principle [closed]

Please help me solve this problem: Assuming that in a box there are $10$ black socks and $12$ blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the ...
-1
votes
1answer
74 views

Prove that two non-bald residents of NYC have exactly the same number of hairs.

In New York City there are two non-bald people who have the same number of hairs ( the human head can contain up to several hundred thousands with maximum of about 500,000) How can I prove the ...
0
votes
1answer
22 views

Question about use of pigeonhole principle to show that there are at least 3 common neighbors to two vertices

Let $G$ be a simple graph such that $|V|\ge 5$, also $x,y$ are vertices that aren't adjacent. Prove that if $d(x),d(y)\ge \frac {n+1}2$, then $x,y$ has at least $3$ common neighbors. My attempt: ...
1
vote
1answer
68 views

Problem with the application of the pigeonhole principle.

A football team plays at least one match per day in a month of $30$ days , but no more than $45$ matches in that month. Is it true that in some consecutive days in the month, the team will play ...
3
votes
2answers
69 views

Is my argument correct to solve this textbook problem?

The problem is from M.Bona's "A Walk through Combinatorics", Ch1 Prob 13: There are infinitely many pieces of paper in a basket, and there is a positive integer written on each of them. We know ...
3
votes
2answers
153 views

Why is the Ramsey`s theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramsey`s theorem is a generalization of the Pigeonhole principle source But does not say why this is true. I am doing a presentation about the Ramsey theory and also ...
0
votes
2answers
58 views

How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects?

Example: How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3? I understand how to do it when we need to make sure that at least ...
1
vote
1answer
96 views

Pigeonhole principle, choosing 1-8 numbers out of 27

prove that for every 8 choosen numbers from 10 to 36 you can always make equalities. number can be used once. examples. let say that the choosen numbers are 10, 11, 12, 15, 18, 25, 32, 36 you can ...
7
votes
1answer
118 views

$n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil $ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil $ different distances ...
6
votes
5answers
694 views

Given 5 integers show that you can find two whose sum or difference is divisible by 6.

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" ...
0
votes
2answers
71 views

Pigeonhole question with finding a number.

Show that there is a number consisting only of 1’s that is divisible by 2001. I know that it relates to the Quotient-Remainder Theorem and I got m=2001q+r, r: [0,2001). But I don't know how it ...
4
votes
1answer
145 views

Students knowing others

There are 25 students in the class. It is known that among any three of them, two know each other. Show that there is a person who knows at least 12 other people. Thoughts: I know this is true since ...
1
vote
3answers
75 views

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays each. Miklos Bona rates this question as "less difficult than average" while I am stuck on it although I ...
-5
votes
1answer
35 views

Discrete Structures camper problem [closed]

If a camp has 12 cabins, what is the smallest number of campers that will guarantee that at least one cabin has more than six people? Please explain each step- I'm confused about how to do this.
4
votes
4answers
101 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
2answers
37 views

How to show $x,y,z \in A$ - Functions, Combinatorics

If $A \subseteq \{1,2,3,4,5,6\}$, how to show that for every $A$ there are $x,y,z \in \{1,2,3,4,5,6\}$, where $x,y,z$ can also be the same or at least not different from each other, and the following ...
2
votes
2answers
63 views

Pigeonhole Principle question - sum of natural numbers

Let $f:\{1,2,...,15\} \rightarrow \Bbb N$ be a function such that $\sum_{i=1}^{15} f(i) =100$. $f(15+1)$ is defined to be $f(1)$. I have shown that $14\leq f(i)+f(i+1)$ for some $1\leq i \leq15$ ...
-1
votes
1answer
46 views

Pigeonhole principle, choosing point in a region [closed]

Consider the following region: It is bounded by a regular hexagon whose sides are of length 1 unit. Show that if any 7 points are chosen in this region (hexagon), then 2 of them must be no further ...
1
vote
1answer
57 views

51 Dalmatians grouping

Suppose there are 51 dalmatians and number of dots on each dalmatian is not null. Prove (or dis-prove) there is always a grouping such that at least one group has total number of dots as multiple of ...
4
votes
3answers
69 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
1
vote
1answer
42 views

Prove that if a graph has six vertices, then at least one of G or $\bar{G}$ has a subgraph isomorphic to $K_3$

I think this proof is related to proving to Theorem on friends and strangers which can be proved with the pigeonhole principle. But I am at a loss as to what are the holes and pigeons in this case. I ...
2
votes
1answer
53 views

pigeonhole principle - Oneway Island

There is a group of cities with the follwoing rule: Each city is connected to each city linked by a oneway street: For any two different cities $A$ and $B$ is it you either go directly from $A$ to ...
0
votes
0answers
51 views

Pigeon Hole Principle - proof of d as a positive integer

Let $d$ be a positive integer and consider any set $A$ of $d+1$ positive integers. Show that there exists two different numbers $x, y\ \epsilon\ A$ so that $ x \mod\ d = y \mod\ d$ and $x =/= y$. ...
3
votes
1answer
72 views

Pigeon Hole Principle : For $n + 1$ numbers

My question is : Take $n + 1$ numbers out of $1, 2,..., 2n$ Show that there will be two consecutive numbers My Approach : Using the Pigeon Hole Principle , the $n$ holes are ...
2
votes
1answer
50 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
0answers
68 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 ...
9
votes
2answers
148 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 ...
2
votes
2answers
98 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 ...
1
vote
1answer
76 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
96 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 ...
0
votes
3answers
64 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
6
votes
1answer
100 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 ...
0
votes
1answer
50 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
62 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
60 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
40 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
85 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
20 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
59 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.?