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

22answers
7k views

### What is your favorite application of the Pigeonhole Principle?

The pigeonhole principle states that if $n$ items are put into $m$ "pigeonholes" with $n > m$, then at least one pigeonhole must contain more than one item. I'd like to see your favorite ...
2answers
1k views

### Chess Master Problem

From Introductory Combinatorics by Richard Brualdi We have a chess master. He has 11 weeks to prepare for a competition so he decides that he will practice everyday by playing at least 1 game a day. ...
2answers
2k views

### Choose 100 numbers from 1~200 (one less than 16) - prove one is divisible by another!

Prove that if 100 numbers are chosen from the first 200 natural numbers and include a number less than 16, then one of them is divisible by another. How to prove this? many thanks....
3answers
814 views

### Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other. Any help is appreciated!
2answers
231 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 ...
1answer
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 ...
3answers
1k views

### A question related to Pigeonhole Principle

In a room there are 10 people, none of whom are older than 60, but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of ...
1answer
727 views

### 101 positive integers placed on a circle

A Pigeonhole Principle problem: 101 positive integers are placed on a circle whose sum is 300. Prove that it is possible to choose from these numbers some consecutive numbers whose sum is ...
2answers
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 ...
11answers
4k views

### Prove that if two miles are run in 7:59 then one mile MUST be run under 4:00.

I'm in an argument with someone who claims that a two mile in 7:59 does not imply that one mile (at some point within the two miles) was covered in under 4:00. This is obviously wrong, but I'm not ...
6answers
5k views

### Of any 52 integers, two can be found whose difference of squares is divisible by 100

Prove that of any 52 integers, two can always be found such that the difference of their squares is divisible by 100. I was thinking about using recurrence, but it seems like pigeonhole may also ...
3answers
848 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
2k views

### if there are 5 points on a sphere then 4 of them belong to a half-sphere.

If there are 5 points on the surface of a sphere then there is a closed half sphere containing at least 4 of them. It's in a pidgeonhole list of problems, but I think I have to use rotations in more ...
4answers
454 views

### Prove that 2 students live exactly five houses apart if

There are 50 houses along one side of a street. A survey shows that 26 of these houses have students living in them. Prove that there are two students who live EXACTLY five houses apart on the street. ...
1answer
267 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 ...
2answers
2k views

### If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
2answers
244 views

### Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
2answers
399 views

### For any arrangment of numbers 1 to 10 in a circle, there will always exist a pair of 3 adjacent numbers in the circle that sum up to 17 or more

I set out to solve the following question using the pigeonhole principle Regardless of how one arranges numbers $1$ to $10$ in a circle, there will always exist a pair of three adjacent numbers in ...
1answer
179 views

### A Pigeonhole Principle Question

Show that in a party of $n$ people, there are two people having identical number of friends. I am a beginner at Pigeonhole Principle problems and have produced a solution to this intermediate level ...
1answer
204 views

### pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
1answer
192 views

### Using the Pigeonhole Principle to show that $2$ of any $n+1$ numbers from $\{1,2,\ldots,2n\}$ sum to $2n+1$

Let n be greater or to 1, and let S be an (n+1)-subset of [2n]. Prove that there exist two numbers in S whose sum is 2n+1. I know I have to use the pigeonhole principle - no idea how to start...
2answers
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$, ...
2answers
239 views

### Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
2answers
182 views

### How are the pigeonholes calculated in this pigeon-hole problem?

The question is as follows: To prepare for a marathon, an elite runner runs at least once a day over the next 44 days, for a total of 70 runs in all. Show that there's a period of consecutive ...
7answers
315 views

### How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
1answer
285 views

### Pigeonhole Principle

Let $X = {x_0, x_1, Â· Â· Â· , x_m}$ be a subset of ${1, 2, Â· Â· Â· , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
2answers
163 views

### pigeonhole principle and division

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its ...
2answers
1k views

### Pigeonhole Principle question

There is a row of 35 chairs. Find the minimum number of chairs that must be occupied such that there are some consecutive set of 4 chairs or more occupied. I would like to have some hints as to ...
2answers
88 views

### Pigeonhole principle application

Say there are $p_{1}$ red balls and $p_{2}$ green balls. We put all the balls in a circle with $p_{1}+p_{2}$ places in total. It is forbidden that a ball (red or green) is placed between two red ...
9answers
7k views

### 100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
6answers
640 views

### Is Pigeonhole Principle the negation of Dedekind-infinite?

From Wiki, "The Pigeonhole Principle": In mathematics, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more ...
5answers
5k views

### Show me some pigeonhole problems [closed]

I'm preparing myself to a combinatorics test. A part of it will concentrate on the pigeonhole principle. Thus, I need some hard to very hard problems in the subject to solve. I would be thankful if ...
0answers
283 views

### How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

This a shortened version (motivation from telecommunications stripped away) of a question I asked in MO in late May (no answers). I am mostly checking, if somebody has seen this or a related question ...
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 ...
1answer
334 views

### Pigeonhole principle for a triangle

Consider a equilateral triangle of total area 1. Suppose 7 points are chosen inside. Show that some 3 points form a triangle of area $\leq\frac 14$.
3answers
479 views

### Prove that the product of primes in some subset of $n+1$ integers is a perfect square.

I am trying to prove the following: The set $A$ consists of $n + 1$ positive integers, none of which have a prime divisor that is larger than the $n$th smallest prime number. Prove that there ...
2answers
296 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 ...
2answers
7k views

### In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc ...
1answer
134 views

### $n$ points in the plane: show there are at least $\lceil \frac{n}{3} \rceil$ different distances between pairs of points

How can I prove that in each group of $n$ points in the plane, such that there are not $3$ points on the same line, there are at least $\left\lceil \frac{n}{3} \right\rceil$ different distances ...
4answers
122 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 ...
4answers
980 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 ...
1answer
117 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 ...
2answers
255 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!
1answer
368 views

### If any x points are elected out of a unit square, then some two of them are no farther than how many units apart?

If 5 points are randomly positioned in a unit square, no two points can be greater than square root of 2 divided by 2 apart; divide up the unit square into four squares, and, based on the pigeonhole ...
3answers
110 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 ...
2answers
136 views

### Polygon and Pigeon Hole Principle Question

Seven vertices are chosen in each of two congruent regular 16-gons. Prove that these polygons can be placed one atop another in such a way that at least four chosen vertices of one polygon coincide ...
1answer
217 views

### Arrangement of $100$ points inside $13\times18$ rectangle

Prove that you can't arrange 100 points inside a $13\times18$ rectangle so that the distance between any two points is at least 2. I tried many ways to divide the rectangle, but I can't get the ...
2answers
170 views

### Pigeonhole principle and a decagon

This is a homework Question and has to do with Pigeonhole principle. Could use a hint. Q. The numbers ${0,1,2,.....9}$ are randomly assigned to the vertices ${x_0,x_1,...x_9}$ of a decagon. Show that ...
5answers
509 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 ...
2answers
140 views

### Pigeonhole principle: In every set of 100 integers, there exist two integers whose difference is a multiple of 37

What are the pigeons and the pigeonholes and how to prove this statements? At first I tried to the following: There are "100 choose 2" or 4950 pairs of integers. But I don't know how to move ...