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

3
votes
1answer
44 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
53 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
38 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
48 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
44 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
57 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
votes
0answers
86 views

Terrible at combinatorics

Okay, so let me make a declaration first: I AM TERRIBLE AT COMBINATORICS. I get along fine with finding no. of ways certain things can be arranged, etc. but I suck at Pigeonhole Principle and ...
1
vote
1answer
35 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
23 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 ...
3
votes
4answers
118 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...
1
vote
3answers
176 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. ...
9
votes
2answers
183 views

Smallest number of points on plane that guarantees existence of a small angle

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 ...
0
votes
1answer
190 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
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.
2
votes
2answers
140 views

Solve using Pigeonhole principle

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44. How can I prove this using pigeonhole ...
0
votes
1answer
62 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
91 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 ...
6
votes
2answers
886 views

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This looks like a difficult problem: Is there among first $100000001$ Fibonacci numbers one that ends with $0000$? (it is from a competition training; trainer suggests using pigeonhole ...
7
votes
5answers
4k 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 ...
3
votes
2answers
98 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
32 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 ...
7
votes
4answers
3k views
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 ...
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 ...
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
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 ...
1
vote
1answer
48 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 ...
0
votes
1answer
45 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 ...
1
vote
1answer
67 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$ ...
13
votes
2answers
556 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 ...
2
votes
1answer
55 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 ...
3
votes
2answers
67 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?
4
votes
4answers
223 views

Pigeonhole principle (I think): colored points in the plane

Suppose that each points in $\Bbb R^2$ is colored red, green or blue. Prove that either there are two points of the same color a distance $1$ unit apart, or there is an equilateral triangle of side ...
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 ...
0
votes
1answer
165 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 ...
2
votes
1answer
79 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
54 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
38 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
397 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
63 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 ...