Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

6
votes
5answers
683 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" ...
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 ...
-5
votes
2answers
46 views

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

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.
3
votes
4answers
95 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.
0
votes
3answers
533 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 ...
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
87 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 ...
55
votes
22answers
6k views

What is your favorite application of the Pigeonhole Principle?

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 ...
3
votes
1answer
67 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 ...
7
votes
2answers
495 views

Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other. Any help is appreciated!
1
vote
1answer
31 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
574 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
59 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
46 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
71 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
21 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
67 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
68 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 ...
0
votes
2answers
84 views

Discrtete math proof by contradiction problem

I have the following problem that I must prove by CONTRADICTION: "Show that if you pick three socks from a drawer containing just blue socks and black socks, you must get either a pair of blue socks ...
0
votes
1answer
91 views

Proof of the pigeonhole principle by contradiction

I'm trying to prove this pigeonhole problem: Given that fact that $\lceil x \rceil < x + 1$, give a proof by contradiction that if $n$ items are placed in $m$ boxes then at least one box must ...
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
141 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 ...
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
3answers
74 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.
-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
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
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
68 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 ...
6
votes
2answers
861 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.
9
votes
2answers
146 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 ...
5
votes
4answers
779 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
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$. ...
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 ...
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 ...
3
votes
1answer
171 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 ...
2
votes
1answer
147 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 ...
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
1answer
63 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
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 ...
15
votes
6answers
545 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 ...