Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

1
vote
2answers
67 views

From any list of $131$ positive integers with prime factor at most $41$, $4$ can always be chosen such that their product is a perfect square

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem. BdMO 2010 In a set of $131$ natural numbers, no number has a prime factor greater than 42. ...
1
vote
2answers
53 views

Pigeon Hole Principle on a set of n elements

Homework question: It is asking us to prove that if we have $\frac{n}{2} + 1$ integers selected from a set$ A = {1, 2, ..., n}$, $n$ being an even integer, then the selection includes integers $x$ ...
1
vote
2answers
924 views

If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1.

Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it! I am asked to prove this using the pigeonhole principle: ...
1
vote
2answers
197 views

Prove a number is even using the Pigeonhole Principle

Let n be an odd integer and let f be an [n]-permutation of length n, where [n] is the set of integers 1, 2, 3,...n Show that the number ...
1
vote
2answers
105 views

Pigeonhole Question

This is an example from a Discrete math textbook: Any subset of size $6$ from the set $S = \{1,2, 4, \dots 9\}$ must contain two elements whose sum is $10$. Answer: Here the pigeons constitute a $6$ ...
1
vote
1answer
78 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 ...
1
vote
2answers
203 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 ...
1
vote
2answers
80 views

Counting Subset Properties

Let $N=\{1,2,...,100\}$ and $A$ be a subset of $N$ with $|A|=55$. Show that $A$ contains two numbers with difference $9$. Is this also true for $|A|=54$? I was trying to solve this via the pigeonhole ...
1
vote
1answer
91 views

Twenty distinct integers are chosen from {1,2,…,69}. Prove that amongst their pairwise differences there are at least four which are identical.

I understand that the set {1...69} is arbitrary. I'm having a hard time proving it. Should I prove through induction or use the pigeon hole principle?
1
vote
2answers
130 views

pigeonhole principle and division

How is it possible to prove with the use of the pigeonhole principle that in every set of 2012 different numbers that are bigger or equal to zero there is at least one subset that if you sum up its ...
1
vote
1answer
98 views

Pigeonhole Principle Question: Given any 5 points inside a square of side length 2, there is always a pair whose distance apart is at most $\sqrt2$

The question I am looking at: Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$. This looks to me like I ...
1
vote
1answer
37 views

$[x-\frac{1}{n}, (n-1)x+\frac{1}{n}]$ contains an integer $\forall x\in \mathbb{R}$ and $\forall n\in \mathbb{N}$

For any real number x: Prove that among the numbers x,2x,...,(n-1)x ,there is one that differs from an integer by at most $\frac{1}{n}$. any hints for a pigeon solution. Non-pigeon solution ...
1
vote
1answer
63 views

In a class of 50 students, how many students are guaranteed to get the same score on an equally-weighted 20 question quiz?

I am completely lost... Any help is greatly appreciated. I am unsure where to go to better understand the concepts behind this problem. The problem: In a class of 50 students, how many students are ...
1
vote
1answer
42 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 ...
1
vote
3answers
96 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
3answers
101 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 ...
1
vote
1answer
129 views

Pigeonhole problem

I'm struggling with this problem for a while now, and I just can't figure it out. Prove: Let $n_1, n_2, . . . , n_t \in \mathbb{N}^+$ If $n_1 + n_2 + . . . + n_t-t + 1$ Objects are laid in t ...
1
vote
2answers
89 views

Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$.Prove that multiplication two number of these numbers are complete square

Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$ is formed. Prove that multiplication two number of these numbers are complete square. Thank you.
1
vote
2answers
67 views

graph-theory combinatorics

Here is a combinatorics problem having to do with graph-theory Ten players participate at a chess tournament. Eleven games have already been played. Prove that there is a player who has played at ...
1
vote
1answer
344 views

Pigeonhole principle question

Suppose a graph with 12 vertices is colored with exactly 5 colors. By the pigeonhole principle, each color appears on at least two vertices. True or false? The correct answer is false, but I assumed ...
1
vote
1answer
63 views

Choosing $2n-1$ points from $n\times n$ grid such that $3$ points always form a right triangle

NOTE: Looking for a hint,not the whole solution. BdMO 2012 Nationals Secondary Consider a $n×n$ grid of points. Prove that no matter how we choose $2n-1$ points from these, there will always ...
1
vote
2answers
40 views

combinatorics - permutations question, possibly with pigeon hole

Let $A \in Mat_n(\mathbb R)$ such that $\forall i,j: a_{ij}\geq 0$ We are given: $$\forall j: \sum_{i=1}^n a_{ij}=\sum_{i=1}^n a_{ji}=1$$ show there's a permutation $\pi \in S_n$ such that $$\forall ...
1
vote
1answer
43 views

Composite Polynomials over UFDs

I was sitting in the Math room at my school and was reading the AMA Monthly and came across the proof for the following problem: Let $R$ be any UFD that is not a field. Suppose that $R$ has only ...
1
vote
3answers
153 views

Generalized Pigeonhole Principle

Can somebody explain this to me? I am very confused. I have a question that says "What is the minimum number of students required in a discrete mathematics class to be sure that at least six will ...
1
vote
1answer
56 views

Pigeonhole problem - salvaging my solution

A student is solving combinatorics problems. Each day he solves at least one problem. He solves no more than 500 problems a year. Prove that there is an interval of days in which he solves 229 ...
1
vote
1answer
65 views

How do you tell which are the pigeons and which are the pigeon holes? [closed]

I am unable to correctly identify pigeons and pigeon holes in word problems. What is the technique?
1
vote
2answers
81 views

90 people with ten friends in the group. Prove its possible to have each person invite 3 people such that each knows at least two others

A high school has 90 alumni, each of whom has ten friends among the other alumni. Prove that each alumni can invite three people for lunch so that each of the four people at the lunch table will know ...
1
vote
2answers
67 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 ...
1
vote
1answer
94 views

birthday problem help

For the birthday problem, how many people are needed to ensure that at least three people are born in the same month? After looking at the problem I think the answer would be 25 because 12 + 12 + 1? ...
1
vote
3answers
292 views

Pigeon hole birthday problem?

If there are 10,000 people, how many people must have the same birthday (ignoring year)? This is the way I went about this problem: 10000 people / 365 days in a year = 27.397 people per day ...
1
vote
2answers
101 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 ...
1
vote
1answer
29 views

Proving minimum exsistence of intersection cardinality

Let $F_1,F_2...F_{13}$ be sets such that $\forall 1\le i \le 13: F_i\subseteq [10]$ and $|F_i|=6$ when $[10]={1,2,3...10}$ prove that there are $1 \le j < k < l \le 13$ such that $|F_j \cap F_k ...
1
vote
1answer
85 views

Is there a Pigeon hole principle proof

Let $a_i$, $1 \leq i \leq 5$ denote five positive real numbers such that $\sum_{i =1}^{5}a_i = 100$. Show that there exist a pair $a_i,a_j$ such that $|a_i-a_j|\leq 10$. Is there a proof using pigeon ...
1
vote
1answer
59 views

Pigeon hole principle?

A guy reads a book. He read for 81 hours last 10 days. Prove that there has been two consecutive days when he read for at least 17 hours. 81 hours / 10 days equals 8,1 hour a day. 2 * 8,1 = 16,2. It ...
1
vote
1answer
57 views

Pigeonholing mod 4 points on plane.

I have the following problem as homework. Suppose there are 13 points in the plane, all with integer coordinates. Prove at least one quadrilateral with vertices on those points has a barycentre with ...
1
vote
1answer
53 views

If $n\nmid a,a+d,a+2d. . . a+(n-1)d$,then $(n,d)=1$

None of the numbers in the sequence $a,a+d,a+2d,a+3d. . . a+(n-1)d$ are divisible by $n$.Then we have to prove that d and n are coprime. I am supposed to use the pigeonhole principle for this ...
1
vote
1answer
64 views

pigeonhole principle related problem

I'm given the problem: In a tournament which 18 teams participate, a team being matched with another in a round don’t match again in the follwoing (later) rounds. After 8 rounds prove that there are 3 ...
1
vote
1answer
47 views

Arangement of six circles in a plane

Six circles (including their circumferences and interiors) are arranged in the plane so that no one of them contains the center of another. Prove that they [the six circles] cannot have a point in ...
1
vote
1answer
47 views

Pigeonhole question - divisibility by chosen number

This question should be solved with pigeonhole principle. Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number. Show that ...
1
vote
1answer
73 views

Pigeonhole Principle question - sum of positive integers

A question that should be solved with pigeonhole but I'm having problems. $a_1,a_2,a_3,...,a_{77}$ are positive integers. We are given that $a_1+a_2+a_3+...+a_{76}+a_{77} < 133$ Show that there ...
1
vote
2answers
54 views

Max area of triangle -PHP

How do i prove that the maximum area that can be obtained among 3 random points in a square is half the area of the square?- I need it to for the following question " Show that among any 9 points ...
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 ...
1
vote
1answer
36 views

Min Number of Values from {1,2,…,9} Such that diff of 2 picked values is 5

This is a question from Shcaum's whose answer I don't understand. Our textbook has 2 pages on the pigeonhole principle and I'm having quite a bit of difficulty with it. Give the set ${1,2,...,9}$ ...
1
vote
1answer
43 views

Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
1
vote
1answer
62 views

Combinatorics pigeonhole principle question.

There are $n$ people at a meeting, each of whom chooses $3$ distinct numbers between $1$ and $11.$ $\quad({\sf a})$ What is the smallest value of $n$ which guarantees that at least two people choose ...
1
vote
1answer
58 views

My first proof employing the pigeonhole principle / dirichlet's box principle - very simple theorem on real numbers. Please mark/grade.

What do you think about my first proof employing the pigeonhole principle? What mark/grade would you give me? Besides, I am curious about whether you like the style. Theorem Among three elements ...
1
vote
0answers
50 views

$x_1,x_2,\ldots,x_m$ is a permutation of $1,2,\ldots,m$ and $n_1,n_2,\ldots,n_m$ be integer and $m>1$ and odd.

$x_1,x_2,\ldots,x_m$ is a permutation of $1,2,\ldots,m$ and $n_1,n_2,\ldots,n_m$ be integer and $m>1$ and $m$ is odd. Now, $f(x)$ be defined as $f(x)=\sum\limits_{i,j=1}^{m} n_ix_j$. If $a,b$ are ...
1
vote
0answers
59 views

How to estimate pigeonhole principle?

I was thinking about this after my professor mentioned the pigeonhole principle in class. Let's say we have $N$ items and $M$ containers. Here we assume $N > M$. We will randomly place each of the ...
1
vote
1answer
50 views

Combinatorics - possibly pigeon hole, 100 by 100 matrix with numbers from 1 to 100

We are given a $100$ by $100$ matrix. Each number from $\{1,2,...,100\}$ appears in the matrix exactly a $100$ times. Show there is a column or a row with at least $10$ different numbers. I'd like a ...
1
vote
0answers
132 views

Friend Group and Hater Group

Consider a set $S$ of $n$ people such that, for all distinct $x$ and $y$ in $S$, it is the case that either $x$ and $y$ like each other or $x$ and $y$ hate each other. Let us call $S' \subseteq S$ a ...