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.

3answers
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.
1answer
84 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 ...
0answers
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 : ...
3answers
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 ...
1answer
99 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 ...
3answers
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 ...
3answers
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 ...
3answers
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 ...
1answer
42 views

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

1answer
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. ...
5answers
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$ ...
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?
2answers
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 ...
3answers
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 ...
3answers
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. ...
0answers
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.
1answer
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 ...
0answers
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 ...
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!
3answers
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 ...
1answer
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 ...
1answer
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 ...
4answers
539 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?
1answer
48 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 ...
1answer
100 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 ...