# Tagged Questions

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.

102 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 ...
82 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.
86 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 ...
49 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 $\frac{1}{n}$ My approach : ...
67 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 ...
100 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 ...
60 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 ...
85 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 ...
50 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 ...
42 views

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?
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 ...
640 views

44 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. ...
410 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 $79$ ...
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?
65 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 ...
247 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 ...
204 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. ...
111 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.
48 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. My ...
46 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 ...
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!
849 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 ...
66 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 ...
76 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 ...
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 ...