Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then one at least one container has more than one item.

learn more… | top users | synonyms

1
vote
1answer
76 views

Generalized pigeonhole principle: 15 workstations and 10 servers

Q: Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to ...
0
votes
0answers
38 views

Set Sum Partition problem - Pigeon hole Application

Prove that from every set of 2n integers, you can chose a subset of n elements, such that the sum is divisible by n.
2
votes
1answer
49 views

Find maximal clique in an multigraph with $n$ vertices, where each vertex is colored with $k$ colors.

You are given a multigraph with $n$ vertices. Every vertex is colored with maximum of $k$ colors. If two vertices share a color, there is an edge between them which is colored with that color. (A pair ...
1
vote
1answer
79 views

Pigeonhole Principle and sets homework

Can someone help me with this question? I'm having trouble solving this problem. I don't know where start. Let $S$ be a set of integers with the following properties: Every element of $S$ ...
0
votes
1answer
49 views

Geometry pigeonhole principle problem.

let sets: $A_1 , A_2 , A_3 , ..., A_{13} \subset [10]$ $\forall i : |A_i|=6$ I'm asked to show that there exist $1\le j_1 \lt j_2 \lt j_3 \le 13$, such that: $|A_{j_1}\cap A_{j_2}\cap A_{j_3}| \ge ...
3
votes
2answers
86 views

pigeonhole principle problem 3

Prove: For every group of 1009 positive integers, there exist 2 integers of that group, that their sum or difference divide with 2014 without residue. where do I start?
2
votes
1answer
67 views

pigeonhole principle problem 2

Every year the teacher write 4 tests with 6 questions, from a list of 10 different questions, Is it certain that after 8 years, theres 3 different tests with the same 4 questions? how do i show that ...
13
votes
2answers
575 views

Combinatorics problem (Pigeonhole principle).

let {${a_i}$} $1\le i \le 55$ be a sequence of positive integers (not 0), and $\sum_{i=1}^{55}a_i \lt 95$. And i'm asked to prove that there must exist a sequence $k \lt l$ in $[55]$ , such that ...
0
votes
1answer
189 views

Pigeon Hole Principle (Same sum)

I'm trying to solve this problem using the pigeon hole principle. Suppose you have 2n possible integers $ \big\{x_{1},x_{2},x_{3},...x_{2n}\big\} $ where each integer can be represented using n ...
0
votes
1answer
44 views

What is the minimum number of ordered pairs

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that $$a \equiv c \mod \;3 \;and \;b ...
2
votes
1answer
93 views

Pigeon-Hole Principle Common Sum

Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the ...
-1
votes
1answer
78 views

Pigeonhole principle formula using Propositonal Logic

According to the Pigeonhole Principle, if we try to place $n+1$ pigeons in $n$ pigeonholes, then at least one pigeonhole must have two or more pigeons. For $i \in \{1, 2, \dots, n+1\}$ and $j \in \{1, ...
1
vote
1answer
42 views

How to use pigeonhole principle to demonstrate lower bound in this problem is $\frac{k(n+1)}{2}$?

Background This is not a homework problem, but I am reading through a discrete mathematics book since I am trying to formalize my background in computer science. I came across the following. ...
6
votes
5answers
405 views

Prove that in every sequence of 79 consecutive positive numbers written in decimal system there is a number whose sum of the digits is divisible by 13

Prove that in every sequence of $79$ consecutive positive numbers written in decimal notation there is a number the sum of whose digits is divisible by $13$. I tried to take one by one sets of ...
3
votes
0answers
31 views

Show that if you paint 6 dots on the unit square, then there is always a couple of 2 points with distance <=2/3 [duplicate]

This question is difficult for me. Anyone knows how to divide the unit square by using pigeonhole principle?
0
votes
2answers
63 views

There are 12 children .Assuming there are 4 children’s bedrooms show that there are at least 3 children sleeping in at least one of them.

There are 12 children in the family Assuming there are 4 children’s bedrooms in the house, show that there are at least 3 children sleeping in at least one of them. My question is can I use ...
1
vote
3answers
133 views

Pigeonhole principle: Asking the minimum number of students

The question What's the minimum number of students, each of whom comes from one of the 50 states must be enrolled in a university to guarantee that there are at least 100 who come from the same ...
1
vote
3answers
196 views

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$.

Prove that if four numbers are chosen from the set $\{1,2,3,4,5,6\}$, at least one pair must add up to $7$ using the Pigeonhole principle. I am supposed to identify the pigeons and the pigeonholes. ...
0
votes
0answers
104 views

Out of $513$ nine-digit numbers, there must be two with matching zero positions

Need help figuring this one out, came up in class and I have no idea how to write a proof for this. Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros.
0
votes
1answer
44 views

How many times must we roll a single die in order to get the same score $n$ times?

How many times must we roll a single die in order to get the same score n times for $n\ge 4$? I thought the answer was $6n + 1$ but the answer is $6 (n-1)+1$ and I don't really get why is that. ...
1
vote
0answers
45 views

If $n^2+1$ people are lined up, there are $n+1$ whose heights are increasing or decreasing [duplicate]

Suppose $n^2 +1$ people are lined up shoulder to shoulder is a straight line. Then it is always possible to choose $n+1$ of the people to take one step forward so that going from left to right their ...
1
vote
1answer
69 views

Show that for every set of 18 integers there will be two that are divisible by 17 [closed]

I understand the pigeonhole principle is needed here and I see the solution in the back of the book, but the explanation is week. If anyone could explain step-by-step that would be awesome!
10
votes
3answers
847 views

sum of one hundred numbers

I saw this problem recently. It asks to prove that it is always possible to choose 100 numbers from 200 positive numbers such that their sum will be divisible by 100. Attempt to solve: my first step ...
2
votes
1answer
64 views

Use of pigeonhole principle in ramsey-theorem about monochromatic triangles.

Im trying to prove that for any number n the complete graph with $p(n)$ vertices whose edges have been colored with n colors in some way has a monochromatic triangle (a triplet of nodes that are ...
3
votes
1answer
73 views

What is the minimum of shirts that must be selected to ensure five shirts of the same color are selected?-Pigeonhole Principle

A closet has 3 red, 7 blue and 10 black shirts. What is the minimum number of shirts you’ve to blindfoldedly pick to ensure a. at least 4 of the same color? b. at least 5 of the same color? Soln: I ...
4
votes
4answers
490 views

How to draw Square Diagonal? [duplicate]

Draw a 5x5 square. In 16 of 25 squares draw diagonals in such a way that no diagonal ends touch. How can I do this?
0
votes
1answer
47 views

Prove existence of 5 non-attacking rooks

Problem: There are $41$ rooks on a $10\times10$ chessboard. Prove that there must exist $5$ rooks, none of which attack each other. I could only observe that at least one of rows and at least one ...
4
votes
1answer
64 views

Prove using induction that from a set of $n+1$ numbers from $1..2n$, at least one number will evenly divide another.

Given a set of $n+1$ numbers out of the first $2n$ natural numbers, $1,2,\ldots,2n$, prove that there are two numbers in the set, one of which divides the other. I can't tell if I'm reducing the ...
1
vote
1answer
81 views

Pigeonhole principle for proof

Prove that if a is a natural number, then there exists two unequal natural numbers k and l for which $$ a^k - a^l $$ is divisible by 10. I'm strangely lost on this one. I understand the pigeonhole ...
0
votes
3answers
57 views

Two out of five in a group have the same number of friends…

I recently came across a problem- Prove that in a group of five people,there are two who must have the same number of friends in the group. I assume it must be solved by Pigeon Hole Principle ...
9
votes
2answers
56 views

show that there are at least $\frac{n(n-1)}{2}$elements in this sets

Let $x_{i},i=1,2,\cdots,n$ be real numbers,and such $$|x_{i}-x_{j}|>1(\forall i\neq j)$$ define set $A=\{x_{i}x_{j}+x_{k}|1\le i,j,k\le n\}$,show that $$|A|\ge\dfrac{n(n-1)}{2}$$ How can I go ...
0
votes
1answer
92 views

Lower bound for $R(3, 3,\ldots, 3)$

As part of learning Ramsey numbers I am trying to prove that $R(\underbrace{3, 3,\ldots, 3}_{k\text{ times}}) > 2^k$ using the constructive method. In order to do that one needs to colour the edges ...
3
votes
2answers
61 views

Prove that if $|S| \ge 2^{n−1} + 1$, then $S$ contains two elements which are disjoint from each other.

I'm trying to use the pigeonhole principle to prove that if $S$ is a subset of the power set of the first $n$ positive integers, and if $S$ has at least $2^{n-1}+1$ elements, then $S$ must ...
1
vote
0answers
47 views

Solution of $Connect4^{TM}$

It says here that Connect4 can be won by Player $1$ if their first counter goes in the middle column $4$, a draw if they play in columns $3$ or $5$, and Player $1$ loses everywhere else. As far as I ...
1
vote
1answer
53 views

Tricky probability question which cant be solved using exclusion?

I am confused on how to go about solving this problem- " What is the probability that 2 people in the group have a birthday in the same month out of a)exactly 20 people? b)atleast 20 people" I ...
1
vote
1answer
68 views
2
votes
2answers
76 views

Mathematical induction and pigeon-hole principle

I am trying to prove that if $n$ is even and if $n+1$ integers are chosen from the set $\{1,2,....,2n \}$ then there are always two integers that differ by 2. In my attempt. I try $n=2$, and ...
0
votes
2answers
25 views

Pigeon hole subset problem

For a given N numbers labeled from 1-N, we need to pick M numbers such that there are atleast K pairs of numbers(x,y) which statisfy x+y=N+1? can anyone help me out with this... please?
2
votes
1answer
127 views

Show that if $n+ 1$ integers are chosen from the set $\{1, 2, . . . , 2n\}$, then there always two which differ by $2$.

$n$ is also given to be an even number. So I want to prove this by using the pigeon-hole principle. I would partition the numbers $\{1, 2, . . . , 2n\}$ into $n$ boxes with numbers in each as ...
1
vote
2answers
72 views

How to apply Pigeonhole principle in this question

There are 10 people at a party and each person knows an even number of people at the party. Prove that there are 3 people who know the same number of people. Here we assume that knowing someone ...
1
vote
1answer
63 views

Variation on the “Number of non-bald people in NYC” problem

I have two questions about the following problem, taken from Challenging Problems in Algebra by Posamentier and Salkind: (1) Why is the answer not 1 person? (2) The answer given, without solution, is ...
3
votes
4answers
147 views

Let $S=\{3,4,5,6,7,8,9,10,11,12\}$. Suppose 6 integers are chosen from S. Must there be 2 integers whose sum is 15?

How can I go about solving this Pigeonhole Principle problem? So I think the possible numbers would be: $[3+12], [4+11], [5+10], [6+9], [7+8]$ I am trying to put this in words...
0
votes
1answer
255 views

In a group of 30 people, must at least 3 have been born in the same month? Why?

This is a pigeon hole principle problem and I'm not sure how I can word this to prove that at least 3 have been born in the same month out of 30 people?
0
votes
1answer
73 views

Show that there are at least 2 computers in the network … (Pigeonhole Principle)

A computer network consists of 6 computers. Each computer is directly connected to at least one of the other computers. Show that there are at least 2 computers in the network that are directly ...
4
votes
3answers
228 views

Application of the pigeon hole principle

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows: "During a month with 30 days, a ...
0
votes
0answers
35 views

Proof of Pigeonhole Principle using equipotence and induction

I am attempting to prove the form of the Pigeonhole Principle which states "$\forall n,m \in \mathbb{N}$, the set $\{1,\cdots,n+m\}$ is not equipotent to the set $\{1,\cdots n\} $". Here is my proof ...
2
votes
2answers
113 views

Prove using Pigeon Hole principle.

A chess master who has 11 weeks to prepare for a tournament decides to play at least one game every day but, to avoid tiring himself, he decides not to play more than 12 games during any calendar ...
0
votes
1answer
73 views

Proving by pigeonhole principle that a duocolored 3x9 rectangle will always contain subrectangles whose corners are the same color.

Lets say each square of a 3x9 rectangular board is colored either blue or red. How can I prove mathematically that for any such coloring, the board will always contain a subrectangle (paralell to the ...
3
votes
0answers
36 views

Markov's Inequality and the Pigeonhole Principle

I heard someone in my department claim that Markov's inequality was just a continuous version of the pigeonhole principle. It seemed reasonable, but I'm struggling to make their connection precise. ...
2
votes
1answer
55 views

Are Square and equilateral triangle the only convex regular ngons that can be composed to smaller versions of themselves?

While I was trying to make an analogous question to Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\frac{\sqrt{2}}{n}$ apart, using equilateral ...