Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

5
votes
1answer
1k 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 ...
5
votes
1answer
173 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
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 ...
4
votes
2answers
1k 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$, ...
4
votes
2answers
1k 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
4answers
735 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
3answers
169 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' ...
4
votes
1answer
255 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
3answers
390 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 ...
4
votes
1answer
156 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
162 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 ...
4
votes
4answers
100 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 ...
4
votes
1answer
1k 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
75 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
2answers
255 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
2answers
270 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
178 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
252 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
1answer
107 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 ...
4
votes
1answer
205 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 ...
4
votes
2answers
118 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.
4
votes
1answer
3k 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
531 views

Divisibility and Pigeonhole principle

Given a sequence of $p$ integers $a_1, a_2, \ldots, a_p$, show that there exist consecutive terms in the sequence whose sum is divisible by $p$. That is, show that there are $i$ and $j$, with $1 \leq ...
4
votes
1answer
324 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 ...
4
votes
3answers
67 views

On the distribution of multiples of 7 into intervals of length 11

Say we have two primes, say 7 and 11. We are to consider the positions of the multiples of 7 inside the (7 buckets of) multiples of $11$. So the buckets of 11 are: $[1,11],[12,22],\ldots ,[67,77]$, ...
4
votes
1answer
92 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
266 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
4
votes
1answer
151 views

If one eats $100$ chocolates in $58$ days,then he must be eating exactly 15 chocolates in some consecutive days

BdMO 2014 Nationals $X$ eats 100 chocolates in 58 days,eating at least 1 chocolate per day.Prove that,in some consecutive days,she ate exactly 15 chocolates. I tried using the pigeonhole ...
4
votes
0answers
183 views

Select 100 integers from 1,2,…,200 [duplicate]

Prove that if 100 integers are chosen from 1,2,...,200, and one of the integers chosen is less than 16, then there are two chosen numbers such that one of them is divisible by the other. Thanks in ...
4
votes
1answer
61 views

let $A$ be a set of $n+1$ natural numbers between $1$ and $3n$. Show that there are $a,b \in A$ such that $n \leq a-b \leq 2n$

I'm having difficulties solving this question and would appreciate a nudge in the right direction. I think this is best solved with pigeonhole, but what are the pigeons and what are the holes?
3
votes
3answers
748 views

A problem in discrete math (Pigeonhole principle related)

This question is from the multiple choice test: A circular region is divided by 5 radii into sectors, as shown above. Twenty-one points are chosen in the circular region, none of which is on any of ...
3
votes
2answers
2k views

Subsets with equal sums

I have a problem to solve but I am in need of your help. Subjects with equal sums: Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), ...
3
votes
5answers
426 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 ...
3
votes
2answers
149 views

Pigeonhole Principle - numbers between $1$ and $100$

Of the set $A=${$1,2,...,100$}, we will choose $51$ numbers. Prove that, among the $51$ chosen numbers, there are two such that one is multiple of the other My notes: 1) There are $25$ prime numbers ...
3
votes
1answer
80 views

Prove by using Pigeon Hole Principle

Let $k \in \mathbb Z^+ $. Prove that there exists a positive integer $n $ such that $k|n$ and the only digits in $n$ are 0's and 3's
3
votes
3answers
146 views

How would you prove this theory of computation problem?

I have trouble proving the following statement, I'm supposed to do it for our theory of computation course but since I've been trying for days I'm looking for a hint : What is the smallest value ...
3
votes
1answer
169 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 ...
3
votes
2answers
95 views

Pigeonhole Principle and Geometry

Consider any five points in the plane that have integer coordinates: -Prove that there are two points such that the midpoint of the line segment joining those two points also has integer coordinates
3
votes
2answers
143 views

Why is the Ramsey`s theorem a generalization of the Pigeonhole principle

German Wikipedia states that the Ramsey`s theorem is a generalization of the Pigeonhole principle source But does not say why this is true. I am doing a presentation about the Ramsey theory and also ...
3
votes
2answers
370 views

Pigeonhole Principle: birthdays on same day of week

How many people must be in a room so that at least 10 have a birthday on a Friday? edit: Assume that no two people share the same birthday I'm somewhat confused and see two different ways to ...
3
votes
2answers
141 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 ...
3
votes
1answer
135 views

Lower bound for the number of coin weightings

The book that I am currently studying has the following exercise. Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by ...
3
votes
2answers
152 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 ...
3
votes
3answers
389 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
3
votes
2answers
190 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 ...
3
votes
1answer
67 views

Prove, that in the subset of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums.

Prove, that in the subset with cardinality $25$ of $\{1,\ldots,150\}$ there are two disjoint pairs with the same sums. Well, there are at most $150+149=299$ possibilities of sums. But if we have a ...
3
votes
2answers
113 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 ...
3
votes
1answer
110 views

Generalizations of the pigeonhole principle

Let us place the numbers $1,2,3....,10$ in a random order on a circular table with 10 places. The question is: prove that there are three consecutive numbers with a sum of 17 or more. I know that we ...
3
votes
3answers
172 views

Proof using pigeonhole and greatest integer (floor) function.

The question is to prove that if m is a positive integer then, $$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right] $$ for $x \in ...
3
votes
2answers
59 views

Is my argument correct to solve this textbook problem?

The problem is from M.Bona's "A Walk through Combinatorics", Ch1 Prob 13: There are infinitely many pieces of paper in a basket, and there is a positive integer written on each of them. We know ...