Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

0
votes
1answer
58 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
14 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
58 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
53 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
98 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
39 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
88 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
108 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
74 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 ...
5
votes
4answers
606 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
1answer
82 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
63 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
89 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
98 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 ...
6
votes
2answers
469 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
3answers
66 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 ...
-4
votes
1answer
30 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
45 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 ...
55
votes
21answers
5k 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 ...
1
vote
2answers
35 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
60 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
50 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
63 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
39 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
51 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
853 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
133 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
712 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
48 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
95 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
65 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
164 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
135 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
48 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
65 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
536 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
95 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
75 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
93 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
0
votes
1answer
48 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
61 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
57 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
35 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
81 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
116 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
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 ...