# 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 ...
943 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 ...
645 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 ...
504 views

### Pigeonhole Principle Question: Jessica the Combinatorics Student

Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every day during the $7$ weeks (so, for example, she won't study for $0$ or $1.5$ ...
640 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 ...
344 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$.
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 ...
338 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. ...
351 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$.
### 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 ...