Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

-4
votes
1answer
21 views

Discrete Structures camper problem [on hold]

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
3answers
57 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
votes
1answer
37 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 ...
54
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 ...
0
votes
2answers
29 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
48 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
42 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
54 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]$, ...
0
votes
2answers
58 views

Pigeonhole principle, maximum numbers taken [closed]

42 peoples come to a laundromat in a particular day.There are 12 washing machines and exactly one people use one machine.Show that if no more than 6 people using each machine,then there will be a t ...
1
vote
1answer
31 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
46 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
850 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
124 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
687 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
41 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
86 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
63 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
156 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 ...
0
votes
1answer
110 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
117 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
43 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
63 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
530 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
93 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
68 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
84 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
60 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
47 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
60 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
56 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
34 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
80 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
115 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
19 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
46 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
64 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
137 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
32 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
79 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
57 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
507 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
209 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 = ...
1
vote
2answers
88 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 ...