# 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.

2k views

### General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
178 views

### $x$ is equal to at least $51$ of $a_1,\frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$. Prove that $2$ of $a_1,\ldots,a_{100}$ are equal.

If $x$ is equal to at least $51$ number of the array $a_1, \frac{a_1+a_2}{2},\ldots,\frac{a_1+a_2+\ldots+a_{100}}{100}$, prove that $2$ numbers of the array $a_1,a_2\ldots,a_{100}$ are equal. That's ...
413 views

### Proving an interesting feature of any $1000$ different numbers chosen from $\{1, 2, \dots,1997\}$

Assume you choose $1000$ different numbers from the group $\{1, 2, \dots,1997\}$. Prove that within the $1000$ chosen numbers, there is a couple which sum is $1998$. I defined: pigeonholes: ...
257 views

### regarding Pigeonhole principle

Let A be a set of 100 natural numbers. prove that there is a set B $$B\subseteq A$$ such that the sum of B's elements can be divided by 100 I am stuck for a few days now. Please help!
168 views

### Pigeonhole principle problem involving inequality 0 < |$\sqrt{x} - \sqrt{y}$| < 1

21 integers are selected from {1, 2, 3, ..., 400}. Prove that two of them, say x and y, satisfy 0 < |$\sqrt{x} - \sqrt{y}$| < 1. I am confident you have to use and apply the Pigeon Hole ...
260 views

### Pigeon Hole Problem

Prove that of any 100 different twelve digit numbers (first digit cannot be zero) there are two of them with the same first and fifth digit. I'm new to this principle and need some assistance. I've ...
208 views

### In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?
189 views

### Pigeonhole Principle Problem combo inequality

Prove that for any subset of $\{1,2,3,...,300\}$ with $102$ elements, there exists elements $M$ and $x$ in that subset such that $100<M-x<200$. I think this is a pigeonhole problem, I wanna ...
496 views

### combinatorics: The pigeonhole principle

Assume that in every group of 9 people, there are 3 in the same height. Prove that in a group of 25 people there are 7 in the same height. I started by defining: pigeonhole- heights. pigeons-people....
86 views

### On a strange pigeonhole principle problem

Given distinct integers $a_1, a_2, \cdots, a_{63}$. Prove that there exists $a_i, a_j, a_m, a_n$ such that $(a_i - a_j)(a_m - a_n)$ is divisible by $1984$. I have no idea of how to create the ...
256 views

### Collection of numbers always in increasing or decreasing order

Anyone have any ideas on this question? I think you have to use the pigeon hole principle..but I am not sure about that? The numbers $1,2,3,\ldots,101$ are written down in a row in some order. Is ...
5k views

### Prove that at a party with at least two people, there are two people who know the same number of people…

Okay, now, I really want to solve this on my own, and I believe I have the basic idea, I'm just not sure how to put it as an answer on the homework. The problem in full: "Prove that at a party ...
130 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 ...
118 views

### Problem with $20$ integers less than $70$

20 pairwise distinct integers each less than 70 are taken and their pairwise differences are taken(magnitude of the difference). Show that there always exists 4 equal numbers. I somehow found ...
379 views

### Pigeonhole Principle and Sets

Can anyone point me in the right direction for this homework question? I know what the pigeonhole principle is but don't see how it helps :( Let $n\geqslant 1$ be an integer and consider the set S = {...
2k views

### Combinatorics - pigeonhole principle question

This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition. An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a ...
195 views

### Set theory: Metamath Proof of the Pigeon-Hole Principle, Error?

I have recently came discovered Metamath. Supposedly the language is one that a computer may proof-check. I then began to look at concepts that I am familiar with, and decided to look up the pigeon ...
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" ...
61 views

### Improving statement obtained by Pigeonhole principle

In this MSE question, this statement is proven: Room is cube-shaped, with side 3m. 136 flies fly in it. Prove that at any moment one can encompass 6 flies with a sphere of radius 90cm. Can ...
2k views

### Existance of multiple of $n$ with only 0 and 1 as it's digits [duplicate]

Possible Duplicate: Proof that a natural number multiplied by some integer results in a number with only one and zero as digits I read this somewhere recently: For any natural number $n$, ...
2k views

### Some three consecutive numbers sum to at least $32$

Here's a question we got for homework: We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$. I assume we need the ...
999 views

### Another pigeonhole principle question

Have another question for you today: A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at ...
146 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 bc&...
205 views

### Pigeonhole Principle Homework Problem

Seven boys and five girls are seated (in an equally spaced fashion) around a circular table with 12 chairs. Prove that there are two boys sitting opposite one another. I used 'G' for girls and 'B' ...
531 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?
291 views

### discrete math about Pigeonhole Principle

Prove that any set of $10$ positive integers less than or equal to $100$ will always contain two subsets with the same sum. Can anyone help me with this problem? Thanks.
400 views

### pidgeonhole problem need assistance

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013. This is a problem I had on an exam and I know that ...
180 views

### Math and chess question!

Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?
171 views

### Minimum number of coins to ensure 10 coins of one type are selected

One coin is labelled with the number $1$, two different coins are labelled with the number $2$, three different coins are labelled with the number $3$, $\ldots$ , forty-nine different coins are ...
512 views

### The Pigeon Hole Principle and the Finite Subgroup Test

I am currently reading this document and am stuck on Theorem 3.3 on page 11: Let $H$ be a nonempty finite subset of a group $G$. Then $H$ is a subgroup of $G$ if $H$ is closed under the ...
123 views

### In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers so ...
2k views

### Pigeonhole: Practical Applications in Computer Science

Most of the problems I've seen involving the pigeonhole principle have so far seemed fairly artificial. As I'm studying CompSci I'm interested what kind of practical, real world problems in CompSci ...
269 views

### Application of the pigeon hole principle

There's a problem in my textbook that I'm having difficulties understanding. The solution given skips steps and is hard to decipher. The problem is as follows: "During a month with 30 days, a ...
85 views

### Pigeonhole principle on two coloured circle

Suppose a circle is divided into 200 congruent sectors, with 100 of them coloured red and the other 100 blue. A smaller concentric circle is placed on the larger circle and also so divided and ...
299 views

### Combinatorics Pigeonhole problem

Hello to all! So i have to do this problem: In the course of an year of 365 days Peter solves combinatorics problems. Each day he solves at least 1 problem, but no more than 500 for the year. Prove ...
341 views

### Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
500 views

### Prove two numbers of a set will evenly divide the other

We have a set A of numbers 1, 2, 3... to 200 The question is asking me to prove that if I choose 101 numbers from the set, there will be two such that one evenly divides the other. I know this ...
195 views

### proof using pigeonhole principle

I am struggling to come up with a proof to the following question(from cut-the-knot.org): Prove that if n is odd,then for any permutation $p$ of the set $\{1,2,3...,n\}$ the product P(p) = (1-p(1))(...
268 views

### $16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
165 views

### Students knowing others

There are 25 students in the class. It is known that among any three of them, two know each other. Show that there is a person who knows at least 12 other people. Thoughts: I know this is true since ...
367 views

### 10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
140 views

### If ten points are on a unit square, one pair is at most $\sqrt2/3$ apart

Ten points are placed in a unit square. Show that there is a pair of points at most $\sqrt2/3$ apart. I'm not sure how to proceed with this problem, and have not had any luck so far.
712 views