Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

57
votes
10answers
5k 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 ...
44
votes
20answers
3k 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 ...
42
votes
1answer
904 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 ...
37
votes
6answers
3k 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 ...
22
votes
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 ...
20
votes
1answer
1k 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 ...
13
votes
3answers
452 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 ...
12
votes
6answers
394 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 ...
11
votes
3answers
496 views

Arc sums for a circle of $k$ positive integers whose total sum is $n$

This problem got me thinking about the following more general scenario: Suppose you have $k$ positive integers with total sum $n$, and you arrange them in a circle. Given such an arrangement, you ...
10
votes
2answers
172 views

Proving the same sum of two subsequences by Pigeonhole Principle?

Let m,n be positive integers. Suppose $x_1 , ... x_m$ are positive integers between 1 and n and $y_1 , ... y_n$ are positive integers between 1 and m. Prove that there is a nonempty sub sequence of ...
9
votes
3answers
383 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 ...
9
votes
2answers
603 views

Pigeonhole principle Question: choose 100 numbers from 1~200,

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....
9
votes
2answers
3k 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 ...
9
votes
1answer
166 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$.
8
votes
2answers
228 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$ ...
8
votes
2answers
774 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. ...
8
votes
2answers
105 views

The Probabilistic Pigeon Hole Principle

Many people are aware of the Pigeonhole Principle: If we distribute $n+1$ pigeons into $n$ pigeonholes, at least one hole will contain at least two pigeons. However, much fewer are aware of the ...
7
votes
4answers
376 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. ...
7
votes
2answers
306 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$.
7
votes
1answer
164 views

Proof that Fibonacci Sequence modulo m is periodic?

It's well known that the Fibonacci sequence modulo m (where m is any integer) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. ...
7
votes
3answers
244 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 ...
6
votes
2answers
274 views

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 equal to 200. (I don't know if the word ...
6
votes
2answers
265 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 ...
6
votes
4answers
97 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 ...
5
votes
4answers
149 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. ...
5
votes
2answers
242 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!
5
votes
5answers
113 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 ...
5
votes
1answer
207 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 ...
5
votes
5answers
1k 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 ...
5
votes
4answers
261 views

The pigeonhole principle question

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- ...
5
votes
3answers
152 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 ...
5
votes
3answers
242 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. ...
5
votes
1answer
313 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!
5
votes
1answer
136 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 ...
5
votes
0answers
185 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 ...
4
votes
4answers
536 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 ...
4
votes
2answers
738 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 ...
4
votes
1answer
195 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.
4
votes
1answer
116 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?
4
votes
2answers
198 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 ...
4
votes
1answer
878 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 ...
4
votes
2answers
60 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 ...
4
votes
1answer
115 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$?
4
votes
2answers
190 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 ...
4
votes
3answers
144 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) = ...
4
votes
1answer
213 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 ...
4
votes
2answers
51 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 ...
4
votes
1answer
76 views

Elegant proof of icosohedron property

This problem was question A1 on the 2013 Putnam contest. Is there a better way to solve this problem than just using pigeonhole principle? Specifically, is there a group theoretic way to interpret ...
4
votes
1answer
974 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 ...
4
votes
1answer
991 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 ...