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

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 ...
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 ...
2k views

### A discrete math riddle

Here's a riddle that I've been struggling with for a while: Let $A$ be a list of $n$ integers between 1 and $k$. Let $B$ be a list of $k$ integers between 1 and $n$. Prove that there's a non-empty ...
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 work....
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 ...
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 ...
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 ...
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 ...
933 views

### Prove that if 33 rooks are placed on a chessboard, at least five don't attack one another

The question asks to prove that when 33 rooks are placed on an $8 \times 8$ chessboard that there are a total of 5 rooks that aren't attacking each other. What I know: 64 squares Rooks attack in ...
643 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 ...
601 views

57 views

### show that there are at least $\frac{n(n-1)}{2}$elements in this sets

Let $x_{i},i=1,2,\cdots,n$ be real numbers,and such $$|x_{i}-x_{j}|>1(\forall i\neq j)$$ define set $A=\{x_{i}x_{j}+x_{k}|1\le i,j,k\le n\}$,show that $$|A|\ge\dfrac{n(n-1)}{2}$$ How can I go ...
338 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$.
1k views

### Are there rigorous formulation and proof of the pigeonhole principle?

The well known and intuitive pigeonhole principle states that if $n$ items are put in $m$ containers, and $n>m$, then there is at least one container which has more than one object. I've always ...
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 ...
336 views

### Pigeonhole Principle Application

I guess this is a Pigeonhole Principle application. I tried dividing the cube in various ways, but got nowhere. Maybe there is another approach. In a cube of side of length $9$ there are $1981$ ...
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. ...
350 views

### Combinatorics proof (any set of 16 numbers from 1 to 100 contains repeated sums)

Suppose that $A$ is a set of 16 distinct natural numbers and that $1\leq p\leq100$ for every $p$ in $A$. Prove that $A$ contains 4 different numbers $a$, $b$, $c$, and $d$, such that $a+b=c+d$.
486 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 ...
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.
908 views

### Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
735 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 ...
315 views

### How to recognize a pigeonhole problem?

I'm going to split this into 2 questions, the first I think might have an answer, the second may not. First, is there a general way to recognize a pigeonhole problem as such? I mean are there some ...
739 views

### Olympiad question on Pigeonhole principle

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is the ...
907 views

### Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This looks like a difficult problem: Is there among first $100000001$ Fibonacci numbers one that ends with $0000$? (it is from a competition training; trainer suggests using pigeonhole ...
1k views

### Given 5 integers show that you can find two whose sum or difference is divisible by 6.

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" (...
153 views

### Pigeon Hole. 80 numbered balls

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$. So they can differ ...
410 views

### Prove that in every sequence of 79 consecutive positive numbers written in decimal system there is a number whose sum of the digits is divisible by 13

Prove that in every sequence of $79$ consecutive positive numbers written in decimal notation there is a number the sum of whose digits is divisible by $13$. I tried to take one by one sets of $79$ ...
71 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 ...
67 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 ...
144 views

### Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\sqrt{2}/n$ apart

I know I need to use the pigeonhole principle to prove this, but I don't know exactly how. What I think I could do is divide the unit square into $n^2$ squares. Using Pythagoras theorem, the maximum ...
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$ ...
### $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 ...
Let $n$ be a natural number such that $n \ge 2$ and given complex number $z_1, z_2, \ldots, z_n$ that is contained in an open unit disk centered at origin. Prove that there exists $\epsilon_l = \pm 1$ ...