Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

1
vote
1answer
64 views

English question regarding pigeonhole principle classic question.

Mr. and Mrs. Smith invited four couples to their home. Some guests were friends of Mr. Smith, and some others were friends of Mrs. Smith. When the guests arrived, people who knew each other ...
3
votes
1answer
99 views

pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
2
votes
1answer
153 views

Probability problem- Are there atleast 3 balls with same colour radius and in same box?

The question is as follows, it came in RMO in 1990. It most likely involves probability..as far I think. Two boxes contain between them 65 balls of several different sizes. Each ball is white, black, ...
3
votes
2answers
108 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 ...
0
votes
1answer
53 views

Pigeonhole Principle to solve question straightforward

A store wants to celebrate its anniversary and will give a $200 shopping certi cate to the first customer to enter the store whose birthday is the same as that of two other previously admitted ...
0
votes
1answer
60 views

Need help to prove pigeonhole problem

If we pick n+1 different positive integers with every integer is less than 2n. Prove that we can always find three numbers among these n+1 numbers that one is equal to the sum of the other two ...
0
votes
1answer
65 views

Solve using Pigeonhole principle

There are 45 candidates appear in an examination. prove that there are at-least two candidates in class whose roll numbers differ by a multiple of 44. How can I prove this using pigeonhole ...
-1
votes
1answer
171 views

Area of the triangle [closed]

Choose any 9 points on or within a unit square. Prove that there always exists 3 points such that triangle formed by them has area 1/3
1
vote
1answer
48 views

Midpoints joining integers on a plane lattice

How can you prove that if five nodes of a plane lattice are chosen at random then, the midpoint of the segment between the two points is a lattice point.
3
votes
1answer
92 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 ...
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 ...
1
vote
3answers
209 views

Pigeon Hole Principle Algorithm

The “pigeonhole principle” states that if n+1 objects (e.g., pigeons) are to be distributed into n holes then some hole must contain at least two objects. This observation is obvious but useful. ...
2
votes
2answers
64 views

A combinatorics problem

Given $A = \{a_0, a_1,...,a_m\}$ such that it's a subset of $\{1,2,...,n\}$ where $m>n/2$, and $a_0$ is the smallest number in $A$. Show that $A$ contains two numbers $b$ and $c$ such that ...
0
votes
1answer
82 views

Pigeonhole principle questions

I want to solve the following problems with Pigeonhole principle. Show that in every group of people that have atleast 2 people, we can find couple that know the number of the people in the group.( ...
3
votes
2answers
106 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$?
1
vote
0answers
60 views

Pigeon Hole Principle : Can one of the games be played?

Q: 9 people are in a club. Each of them can play one of the games among Bridge , Hearts & Mahajong. Prove that they can play at least one of the mentioned games.( all games require 4 players.) I ...
2
votes
3answers
96 views

A pigeonhole problem from “Conjecture and Proof”

I don't really know how to start this problem at all. I would like a solution or even hints. "Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$" The chapter in ...
2
votes
1answer
95 views

pigeonhole principle - 100 points in $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 parts ...
0
votes
1answer
72 views

Coloring the Cartesian coordinate

Color every point of $\mathbb{R}^2$ either red (r) or blue (b). Show some rectangle has its vertices all the same color. I know that if you take say 3 points in a row on the x-axis that those three ...
13
votes
3answers
455 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 ...
3
votes
1answer
191 views

Ramsey Type problem (variant of people at a party)

There is $n$ people at a party. Prove that there are two people such that, of the remaining $n-2$ people, there are at least $\lfloor n/2\rfloor-1$ of them, each of whom either knows both or else ...
1
vote
1answer
39 views

No. of functions satisfying a certain condition

This is from an old exam: Let $M$ be a set of functions from $\mathbb{Z}/3$ into itself. What is the least number of elements that $M$ must contain for there to surely be at least two elements ...
3
votes
1answer
74 views

Pigeonhole Proof

Let $n_1,n_2,\ldots,n_t$ be positive integers. Show that if $n_1+n_2+\cdots+n_t-t+1$ objects are placed into $t$ boxes, then for some $i$, $i = 1,2,\ldots,t$, the $i$th box contatins at least $n_i$ ...
0
votes
1answer
58 views

Pigeonhole Principle Help!!!

The nine entries of a $3 \times 3$ grid are filled with the integers -1, 1 and 0. Use the Pigeonhole Principle to prove among the eight resulting sums (three rows , three columns or two diagonals) ...
5
votes
1answer
137 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 ...
2
votes
1answer
53 views

Prove that there exists a numbered socket such that for every orientation, two equal numbers coincide

There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter ...
1
vote
2answers
60 views

Does the Pigeonhole principle apply in this problem?

I came accross this problem a while ago at school during a math contest. I dont remember the exact instruction (word for word) but it went something like : Randomed A and B, 2 natural integer $\in ...
4
votes
1answer
983 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 ...
2
votes
4answers
426 views

Pigeonhole principle: show that a class of nine has at least five male or five female students.

Here is the problem in full, start to finish, with no other special instructions or rules: "If there are 9 students in a class, show that at least 5 must be male or at least 5 must be female. Also, ...
1
vote
1answer
73 views

How many cards should be picked up?

In a standard deck of $52$ cards, what is the minimum number of cards you need to pick up, in order to guarantee that there is a suit with at least $3$ cards? Shouldn't I pick $10$ cards? Please ...
0
votes
1answer
77 views

Please let me know how to do this step by step. I had tried , but no solution yet…

A store has an introductory sale on 12 types of candy bars. A customer may choose one bar of any five different types and will be charged no more than $1.75. Show that although different choices may ...
3
votes
2answers
94 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 ...
1
vote
2answers
112 views

pigeonhole principle homework question

These are Homework question. They are pigeon hole principle questions and I have a very hard time with these unless I have worked on a similar problem before. Q.1. Prove that if we select 87 numbers ...
1
vote
1answer
118 views

pigeonhole principle exercises

I have an exam in combinatorics on friday and the Pigeonhole principle is a part of the material. Can someone give me a reference to a book with the hardest(!) questions in this material? than you ...
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$?
0
votes
2answers
53 views

Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Suppose you have a list of $n$ numbers, $n\geq 2$. Let $A$ be the set of differences of pairs of the $n$ numbers. Prove or disprove that at least one element of A must be divisible by $n-1$. Anyone ...
0
votes
1answer
75 views

Pigeonhole Principle Question…Fifteen different integers from 100 to 199 are given.

Question was too long to fit on title. Fifteen different integers from 100 to 199 are given. Show that it is always possible to select from these 15 integers at least two different sets $\{a_1, ...
3
votes
1answer
116 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 ...
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$.
2
votes
1answer
112 views

An interesting problem using Pigeonhole principle

I saw this problem: Let $A \subset \{1,2,3,\cdots,2n\}$. Also, $|A|=n+1$. Show that There exist $a,b \in A$ with $a \neq b$ and $a$ and $b$ is coprime. I proved this one very easily by using pigeon ...
1
vote
3answers
91 views

Pigeonhole principle application sums and differences

Let $A \subset \{1,2,...,99\}$, prove or disprove the following: a. For $|A| = 27$ b. For $|A| = 26$ There are $2$ different numbers in $A$ that their sum or their difference can be divided with ...
1
vote
2answers
182 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 ...
2
votes
3answers
148 views

One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
0
votes
1answer
67 views

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart.

There are 50 rooms in a line. If there are 26 rooms with girls, prove there are two girls exactly 5 rooms apart. My idea was place 25 girls in into pairs of rooms, and there is no scenario which ...
1
vote
4answers
98 views

Difference of two powers of $3$ divisible by $2011$

How to prove that there exists two powers of $3$ that differ by a number that is divisible by $2011$?
0
votes
3answers
73 views

Pigeon holes principle

Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
1
vote
2answers
145 views

how to apply hint to question involving the pigeonhole principle

The following question is from cut-the-knot.org's page on the pigeonhole principle Question Prove that however one selects 55 integers $1 \le x_1 < x_2 < x_3 < ... < x_{55} \le 100$, ...
4
votes
3answers
145 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) = ...
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 ...
1
vote
3answers
96 views

About the Pigeonhole principle

The principle says that: Let $k$ and $n$ be any two positive integers. If at least $kn+1$ objects are distributed among $n$ boxes, then one of the boxes must containat least $k+1$ objects. In ...