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
76 views

Discrete Math Pigeon-Hole [closed]

How can we solve below problem? Let $X = \{1,2,3,\dotsc,100\}$. If eleven numbers are selected from $X$, show that there are at least two numbers $u$ and $v$ such that $$0 \lt \left| \sqrt{u} - \...
0
votes
1answer
52 views

Size of family $\mathcal F = \{F_1, \ldots, F_m\}$ is at least $\lceil \log_2n\rceil$.

A family $\mathcal F = \{F_1, \ldots, F_m\}$ of subsets of $\{1,2,\ldots,n\}$ is said to be separating if for any two elements $1 \leq i < j \leq n$, there is some set $F \in \mathcal F$ such ...
1
vote
1answer
39 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 $a,...
32
votes
2answers
2k views

A natural number multiplied by some integer results in a number with only ones and zeros

I recently solved a problem, which says that, A positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits. How can ...
6
votes
1answer
72 views

Proving existence of a triangle of area $\leq \frac{1}{8}$

Problem: Given any set $S$ of $9$ points within a unit square, show that there always exist $3$ distinct points in $S$ such that the area of the triangle formed by these $3$ points is less than or ...
3
votes
1answer
45 views

Prove existence of a triangle with least angle $\leq 30$ degrees

Problem: Let $A$ be a set of $6$ points in a plane such that no $3$ are collinear. Show that there exist 3 points in $A$ which form a triangle having an interior angle not $30$ degrees. I am supposed ...
0
votes
2answers
323 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?
3
votes
1answer
48 views

Pigeonhole Principle - permutations

You are given three permutations of $\langle 1,\dotsc, 28 \rangle$. Show that two of them have common sub-sequence of length four. I tried saying that every permutation has $\binom{28}{4}$ ...
4
votes
3answers
145 views

numbers from $1$ to $2046$

We have randomly taken $21$ integers from $1$ to $2046$. Show that we can take $a$, $b$ and $c$ from the previous $21$ integers in a way such that the following inequality holds \begin{equation} bc&...
0
votes
1answer
17 views

Proof of the lack of existence of a Hamiltonian Cycle

Consider a graph of $|V| = 2k+1$ vertices with $k+1$ of those vertices having exactly degree $2$ such that none of those degree $2$ vertices are adjacent to each other. I want to go about proving that ...
3
votes
1answer
53 views

Pigeonhole Principle - round stadium

10 runners are in a round stadium. All of them start running from the same point at the same time. Each one runs in a constant speed $\ r_i>0 $. Prove that for every $\epsilon>0$ there is time $\...
0
votes
0answers
52 views

Generalized pigeonhole principle Question

Question: The island of Tikong has seventeen villages and the rugby board needs to select a squad to be sent to the regional Oceania tournament to be held in Savulevu. What is the smallest size of the ...
0
votes
1answer
31 views

What is the smallest number of a class to guarantee that two students have their birthdays on the same day of the week?

My answer: k=7 days in a week r=2 according to the GPP(Generalized pigeonhole principle) the smallest number N=k(r-1)+1 N=7(2-1)+1=8 therefor 8 will be the smallest number. is this ...
-1
votes
1answer
21 views

What is the Genaralized Pigeonhole Principle? Explain in your own words

My words:It is the least possible number that one can get when placing objects into boxes, given that the number of objects is greater than the number of boxes. Did my wordings correct?
-2
votes
1answer
26 views

Explain Pigeon holes principle in your own words.

my own words explanation: If there is four pigeonholes in which six pigeons uses to lay their eggs, then there is atleast one pigeonhole housing two or more pigeons. Does my wordings correct and ...
0
votes
2answers
28 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
50 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
56 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
73 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 ...
0
votes
1answer
44 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
42 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
37 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 ...
17
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
22 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
50 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
648 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 ...
5
votes
1answer
51 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
29 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
48 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
43 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
39 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
43 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
72 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. ...
11
votes
2answers
320 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 are ...
-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
102 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
76 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
70 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
53 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
59 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
164 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
84 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
64 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
41 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?