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

-1
votes
0answers
39 views

Pigeonhole principle prove or disprove [on hold]

Please help me to prove this statement whether is correct: For all $f:\mathbb{N}\to \mathbb{N}$ and $t\in \mathbb{N}$, there exist distinct $i,j\in\{0,1,...,3^{t+3}\}$ satisfying: $$f(i+k)≡f(j+k) ...
2
votes
1answer
20 views

Half primes in the set

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
59 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 ...
3
votes
0answers
24 views
+50

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" ...
-4
votes
0answers
39 views

Pigeonhole principle question [closed]

Prove or disprove that for all $f:\mathbb{N} \rightarrow \mathbb{N} $ and $t \in \mathbb{N}$, there exist distinct $i,j \in \{ 0,1,…,3t+3\}$ satisfying: $f(i+k)\equiv f(j+k) \ (mod \ 3)$, $ \forall ...
2
votes
1answer
42 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
34 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
33 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
32 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
55 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
294 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
79 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
32 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
97 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
73 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
68 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 ...
-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
82 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
1answer
38 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?
-5
votes
2answers
167 views

Given any 40 people, at least four of them were born in the same month of the year [closed]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
3
votes
1answer
89 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
76 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
67 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
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 : ...
6
votes
3answers
64 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 ...
3
votes
1answer
94 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
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
76 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
35 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 ...
0
votes
1answer
77 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
118 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 ...
3
votes
2answers
103 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
43 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 ...
3
votes
1answer
48 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 ...
0
votes
2answers
78 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.
0
votes
2answers
49 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 ...
7
votes
4answers
3k views

There are 31 houses on north street numbered from 1 to 57. Show at least two of them have consecutive numbers.

I thought to use the pigeon hole principle but besides that not sure how to solve.
1
vote
1answer
43 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
59 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 ...
1
vote
1answer
179 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 ...
0
votes
1answer
70 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,$ ...