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

-5
votes
2answers
78 views

Given any 40 people, at least four of them were born in the same month of the year [closed]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
3
votes
1answer
49 views

Tricky pigeonhole principle question

Say someone is given at least one marble every day for 7 weeks. However, there are never more than 11 marbles given to the person in one week. Prove that there is some period of consecutive days in ...
-2
votes
3answers
61 views

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other. [closed]

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other.
0
votes
1answer
39 views

Pigeonhole Principle(Strong Form) proof

Pigeonhole Principle(Strong Form) says: Let $q_1$,$q_2$,...,$q_n$ are positive integers If we put $q_1+q_2+...+q_n-n+1$ objects into n boxes then box1 contains q1 or more objects xor box2 contains ...
0
votes
0answers
29 views

How to prove members of this series differ from an integer by, at most, 1/n?

Consider the series , where a is a positive real number. a, 2a, 3a, .... (n-1)a Prove that there is one member of this series that differs from an integer by at most 1/n. My approach : Draw a ...
3
votes
2answers
49 views

How does the pigeonhole principle intuitively suggest incorrect computations of probability?

Here is an interesting false computation using the pigeonhole principle. Suppose I am asked to compute the probability that three successive tosses of a fair coin will have the same result. It can ...
2
votes
1answer
81 views

Combinatorics problem; counting in two ways, china 1993

I'm trying to solve the combinatorics problems provided in Yufei Zhao's blog. Can you help me with this one? China (1993): A group of $10$ people went to a bookstore. It is known that ...
2
votes
3answers
50 views

existence of a lattice rectangle in a $13 \times 13$ grid

Problem: Prove that if 53 points are chosen from a $13\times 13$ grid then there will necessarily exist a rectangle whose vertices are among the 53 points chosen. My try: I am guessing we have to ...
1
vote
3answers
61 views

Placing Pandas in a Triangle Pen

I am working on a bit of a silly problem in my introductory discrete mathematics course. I have five pandas that I need to place in a pen, and I have a pen that is the shape of an equilateral triangle ...
0
votes
3answers
37 views

How to implement the generalized pigeonhole principle

There are 10 red, 8 blue, 8 green & 4 yellow pencils inside a box. How many pencils must be selected at least, so we can be sure that there is one pencil of each colour among them (selected ...
1
vote
1answer
25 views

Pigeonhole Principle For Rationals: Is This on Rings?

I am trying to show using the pigeonhole principle that the decimal expansion of a rational must become repeating. I started out by trying to construct the decimal expansion of $\frac{a}{b}$ where ...
1
vote
1answer
36 views

Sum of $n$ positive real numbers is 1. Estimate subsums of k elements.

Sum of $n$ positive real numbers $a_1, ...,a_n$ is $1$. Let $S_k$ be maximal sum of k distinct elements of $a_n$. (they can be equal but must have different indexes). What is $\sup S_k$ and $\inf S_k$ ...
1
vote
2answers
24 views

Doubly stochastic matrix problems.

Assume we have $4\times4$ doubly stochastic matrix $M$. Let us take $4$ elements of $M$, such that each element is taken from unique row and column. There is $4!=24$ ways to do it. For each $4$-tuple ...
0
votes
1answer
65 views

Pigeonhole Principle

There are $n$ pigeons, where $n \in \Bbb N$, $n\ge1$. Out of these $n$ pigeons, $k$ are smart and know about the pigeonhole principle, where $k < n/2$. The remaining $n−k$ pigeons are not-so-smart. ...
5
votes
1answer
93 views

Putnam Problem, Pigeonhole Principle

I have never attempted or considered any contest math problems, but I recently found a page of Putnam Prep problems in a recycling bin on campus and decided to give some a try since I am home for ...
3
votes
2answers
100 views

Show that given seven real numbers, it is always possible take two of them, such that $\left\vert\frac{a-b}{1+ab}\right\vert<\frac{1}{\sqrt{3}}$

Show that given seven real numbers, it is always possible take two of them, such that $$\left\vert\frac{a-b}{1+ab}\right\vert<\frac{1}{\sqrt{3}}$$ The "Pigeonhole principle" states that if $n$ ...
1
vote
1answer
39 views

Guarantee random pair from subset adds up to x

Suppose I take n numbers from the set S = {2, 4, 6, ..., 50}. How big does n have to be in order to guarantee that, among the numbers I take, some pair will add to 42? I'm very confused on how to do ...
2
votes
1answer
33 views

Integer Lattice Points

Let $(n_1,m_1),(n_2,m_2),. . .,(n_9,m_9)$ be integer lattice points in the plane (ie. $n_i$ and $m_i$ are integers). Show that the midpoint of the line joining some pair of points is also an integer ...
0
votes
2answers
75 views

The Basic Principle

In any n+1 integers there will be a pair which differs by a multiple of n. I have tried to create a pigeon hole with numbers a0,a1,a2,...,an but i could not get a solution.
0
votes
2answers
46 views

Pigeonhole Principle, find the total number [closed]

There are 15 different coffee flavours at the cafe. Oddly, each student in my 8 am class has a favourite flavour there. There are just enough students in the class so you can be absolutely sure that 4 ...
7
votes
4answers
3k views

There are 31 houses on north street numbered from 1 to 57. Show at least two of them have consecutive numbers.

I thought to use the pigeon hole principle but besides that not sure how to solve.
1
vote
1answer
33 views

Show that the sum of a run of integers is divisible by $n$

Here is the problem: Let $a_1,a_2,...,a_n$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+...+a_{k+r}$$ is divisible by $n$. My thoughts: I suppose we ...
0
votes
1answer
49 views

Show that in a group of seventeen people, there exists a trio who are either three mutual friends, three mutual enemies, or three mutual strangers.

Suppose that in a group of people that any two people are either friends, enemies of strangers. Show that in a group of seventeen people, there exists a trio who are either three mutual friends, three ...
1
vote
1answer
145 views

How many ID numbers must you have to guarantee that at least two of them sum to the same number?

ID numbers all have 7 digits from 0 to 9. We will assume that all digits can be 0 through 9 This is a homework problem, but I am afraid I am very lost, though I think I am over thinking it. I know ...
0
votes
1answer
67 views

70 distinct positive integers that are ≤ 200, there must be two whose difference is one of 4, 5, or 9

Prove that among $70$ distinct positive integers that are $≤ 200$, there must be two whose difference is one of $4, 5,$ or $9$. So from this there are $582$ possible pairs whose difference is $4,5,$ ...
1
vote
1answer
50 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
31 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
45 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
69 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
46 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
68 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
56 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
557 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
166 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
38 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
80 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
57 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
39 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
398 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
29 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
58 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
64 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
178 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
58 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
39 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
44 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
68 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
837 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
60 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
63 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 ...