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

0
votes
2answers
23 views

For irrational real number $r$, find $n \in \mathbb{Z}$ such that $|nr - [nr]| < 10^{-10}$.

This problem is from the book "A Walk Through Combinatorics" by Richard Bona. For any irrational number $r$, there exists a positive integer $n$ such that the distance of $nr$ from the nearest ...
6
votes
1answer
43 views

Max size of $B \subset \{1, 2, \ldots, 3n+1\}$ for which no distinct $x, y, z \in B$ have sum in $B$

Given a set $$A=\{1,2,3,\ldots,3n,3n+1\},(n\in N^*)$$ Let $B$ be a subset of $A$, such that for any distinct $x, y, z\in B$, we have $x+y+z\not \in B$. Find the maximum number of elements $B$ ...
3
votes
1answer
50 views

Pigeonhole problem - Can solve it but can't model how it works…

So we have the below pigeonhole problem from an example quiz and I understand how to solve the problem, but I can't really model how it is working in my head. Can anyone explain it? There are 50 ...
0
votes
0answers
72 views

Mantissa of $\pi$ and pigeonhole

It might be worth noting that this is a "pigeonhole principle" problem, but I'm not sure how to use PHP with it. The mantissa of $\pi$ is the fractional part of it (i.e. everything after the decimal ...
-4
votes
0answers
44 views

discrete math , pigeonhole principle problem

Any insights about this problem (discrete math) (proof with pigeonhole) Let $$S=\{1,2,......,2^n-3,2^n-2\}$$ $n$ is natural. We choose,arbitrary, ($n$) numbers from the set $S$. Prove that among ...
0
votes
1answer
36 views

Pigeon Hole Priciple and Genaralized Pigeon Hole Principle Question

Question: What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, $A, B, C, D$, and ...
0
votes
1answer
38 views

Pigeonhole Principle Painting a Plane

I need help with this question, because I do not understand some points. PidgeonHole Question: Paint every point of the plane with either blue or red color. Show that there are 2 points on the plane ...
1
vote
0answers
35 views

12 numbered pigeonholes and balls [duplicate]

This problem was inspired by this James Randi challenge. Given $12$ numbered ($1$ to $12$) pigeonholes and $12$ numbered balls (also from $1$ to $12$); what is the probability that a random ...
16
votes
4answers
6k views

What is the smallest number of people in a group, so that it is guaranteed that at least three of them will have their birthday in the same month?

How should I begin solving this? I know that for months, there are 12, and 3 people from a small group suppose to have birthdays in the same month. Do I just multiply $12\times 3 = 36$ people? Or ...
1
vote
1answer
19 views

Finding a binary column vector that makes all rows distinct

Say I have a collection $\mathcal{M}$ of distinct binary matrices $M_i$, $i = 1, \dots, \binom{k+1}{k-1}$ of size $2^{k-1} \times (k-1)$ where in each $M_i$, all rows are distinct (note: $M_i$ is not ...
1
vote
2answers
49 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 ...
1
vote
3answers
630 views

How many people do you need to guarantee that two of them have the same initals?

An auditorium has a seating capacity of 800. How many seats must be occupied to guarantee that at least two people seated in the auditorium have the same first and last initials? I thought $26 \cdot ...
0
votes
2answers
296 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?
5
votes
1answer
50 views

Application of Jacobi's Theorem in Box Principle

Today I was going through Problem Solving Strategies by Arthur Engel, and found this in the chapter Box Principle Before the question it says it "treats a theorem of Jacobi and its applications" ...
2
votes
1answer
27 views

Half primes in the set [closed]

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
3
votes
2answers
63 views

simple proof for principle of pigeons

I must prove the principle of pigeons but the proofs I find in the internet are too complex. Here's what I can use: Definition $$I_n = \{p\in \mathbb{N}; p\le n\}$$ The principle of the pigeons ...
2
votes
1answer
47 views

Proof related to pigeon hole principle to be done with induction

since the question is about a positive integer m, it's obvious that the use of mathematical induction needed, but to prove the fact for n = k+1 we have to use the pigeon hole principle, i am so ...
0
votes
1answer
41 views

how to find pigeon holes in a question related to pigeon hole principle

prove that every set of 10 two digit numbers has two disjoint subsets with the same sum of elements. In this question i don't know how to choose the pigeon holes, or what will be the pigeon holes
-3
votes
1answer
35 views

Distance between points in a square [closed]

Let $p$ be a square whose side has length $1$. $51$ points are randomly chosen inside the square. Show that there are atleast $3$ points whose mutual distance is $< \sqrt{0.08}$.
1
vote
0answers
34 views

Proving the Pigeonhole Principle

I am looking to prove the Pigeonhole Principle by proving the following claim: Let $A$ be a set with $m$ elements, and let $B$ be a set with $n$ elements, where $m,n\in \omega$ and $m > n$. ...
1
vote
1answer
66 views

A group of $15$ boys plucked a total of $100$ apples. Prove that two of those boys plucked the same number of apples.

A group of $15$ boys plucked a total of $100$ apples. Prove that two of those boys plucked the same number of apples. My answer is: First distribute $90$ apples so that each will have $6$ apples. ...
10
votes
2answers
303 views

Russia (2000) contest:Prove the existence of a pair of rows and columns with intersections differently coloured

We have a $100\times100$ board divided into $10^4$ unit squares. These squares are coloured with four colours so that every row and every column has $25$ squares of each colour. Prove that there ...
-1
votes
1answer
81 views

Show that a class of nine students must have at least three male students or at least seven female students. [closed]

I am stuck with the following problem: Suppose that there are nine students in a class. Show that the class must have at least three male students or at least seven female students. Please help me ...
0
votes
0answers
52 views

Applying pigeonhole principle to determine whether a list of strings must have duplicates.

Say you have a program that creates strings of lower-case letters of length 5 or less. It is told that the program holds 600,000 words on its drive. How can you figure out if all the words are ...
1
vote
1answer
35 views

Pigeonhole Principle - If I play a hand of Texas Hold 'Em per minute for a day, prove I will be dealt a particular pair of cards at least twice.

I'm a little stuck on the size of my sets. Here is what I have so far. Proof. Let $A$ denote the set of possible hands in Texas Hold'em. Since order doesn't matter and repeats are not allowed, ...
1
vote
1answer
99 views

Show that there are always two teams who played exactly the same number of games.

So i was given this question. There are 11 teams in a league. Each team can play against the other team only once. Show that there are always two teams who played exactly the same number of games. My ...
3
votes
1answer
40 views

7 points on a closed disk, one must be the center

I am trying a pigeonhole strategy for proving this assertion of a MO test: "Given 7 points on a closed disk of radius 1 such that the distance between any two of this points is at least one, then one ...
1
vote
1answer
75 views

Choosing $7$ numbers from $[1,2,…,11]$ will give us $2$ that have sum $12$.

Choosing $7$ numbers from $[1,2,...,11]$ will give us $2$ that have sum $12$. I tried: There are only $5$ pairings possible: $(7,5),(8,4),(9,3),(10,2),(11,1)$ Suppose I pick $6$, and then not to be ...
0
votes
2answers
69 views

Cards and columns?

I have a deck of cards which I arrange in 4 rows (13 columns). If I pick one card from each column, how do I show that it's possible to get one card from each rank? I know that I have to use the ...
2
votes
1answer
52 views

How can we prove that every sequence of $30$ elements from a set of three repeats a subsequence of length 3?

How can we prove that for every series over $30$ elements(included $30$), there must be a "sub" three element series then will repeat itself? (Series's numbers are only $\{1,2,3\}$) Example for a ...
3
votes
1answer
57 views

An upper bound on the sum of the lengths of chords

Problem: Several chords are drawn in a circle of radius $1$, and each diameter of the circle intersects no more than four of them. Prove that the sum of their lengths does not exceed 13. I couldn't ...
9
votes
1answer
1k views

Proof that Fibonacci Sequence modulo m is periodic? [duplicate]

It's well known that the Fibonacci sequence $\pmod m$ (where $m \in \mathbb N$) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more ...
-4
votes
1answer
161 views

Pigeonhole Principle - prove that average of 4 integers = average of 2 [closed]

Let S be a set of 10 distinct integers between −10 and 10 (inclusive). Prove that there exist four distinct integers in S whose average is the same as the average of just two of the four.
3
votes
2answers
83 views

Three differences $a_{i}-a_{j}$ are the same

Here is the complete question: ** Consider $2n$ distinct positive numbers (with $n>2$) such that each of them is less than or equal to $n^{2}$. Prove that three differences $a_{i}-a_{j}$ are the ...
0
votes
1answer
61 views

Pigeonhole Principle: sum of 10 people's ages

I am reading through this proof and I have several questions- In the 4th paragraph, it says $111 \times 5 = 555$ why is $111$ being multiplied by $5$? Same goes for why $55$ is multiplied by $5$? ...
0
votes
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 : ...
0
votes
1answer
39 views

Picking Colors of Shirts

If I have a set of 12 shirts comprised of 4 blue, 4 yellow, and 4 red shirts, how many shirts do I have to pick to ensure that there are at least 3 of one color?
1
vote
0answers
34 views

Advanced counting [duplicate]

Someone is throwing a party with $n$ people in attendance( $n \ge 2$ including the host). Why are there at least two people at the party that have exactly same number of acquaintances present?
3
votes
1answer
96 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 ...
6
votes
3answers
65 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 ...
-5
votes
2answers
249 views
3
votes
1answer
90 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
78 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
74 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 ...
2
votes
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 ...
2
votes
3answers
77 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
45 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
30 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
40 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
36 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 ...