Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

1
vote
1answer
188 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 ...
5
votes
2answers
115 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 ...
2
votes
2answers
79 views

A question about the Pigeonhole Principle and linear equations over $\mathbb{Z}$

This may be a bit trivial (apologies if it is), but I was wondering if there was an elementary way to compute the cardinality of the solution set in the following situation: How many solutions would ...
1
vote
1answer
48 views

Show there exists a sequence of days within $49$ days where exactly $20$ hrs. are worked

Assume an integer number of hours will be worked each day for $49$ consecutive days. Further assume that at least $ 1 \frac{\text{hrs}}{\text{day}}$ and at most $11 \frac{\text{hrs}}{\text{wk}}$ can ...
1
vote
1answer
68 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
84 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
1
vote
2answers
58 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
3answers
138 views

Show that for any subset of $10$ distinct integers there exists two disjoint subsets equal in sum

The title abbreviates the following homework exercise on the Pigeonhole Principle. Show that for any set of $10$ distinct integers from $1 \dots 60$ there exists two disjoint subsets of equal ...
2
votes
2answers
54 views

Prove:that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014

Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$). I think the "pigeonholes" here ...
1
vote
1answer
48 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 ...
9
votes
2answers
200 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 ...
1
vote
1answer
82 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 ...
0
votes
1answer
80 views

Probability Pigeonhole Principle

Choose any different 38 natural numbers less than 1000. Prove by using the Pigeonhole Principle that among the selected numbers there exists at least two whose difference is at most 26. I proved an ...
2
votes
1answer
55 views

pigeonhole principle question 40 participants in an art workshop

There are 40 participants in an art workshop. Each one of them signed up for one or more of the following courses: handicraft, ceramics and Chinese paintings. One of the combinations of courses must ...
0
votes
1answer
68 views

pigeons and pigeonhole [closed]

Twenty cards numbered 1 to 20 are placed face down on a table. Cards are selected one at a time and turned over. If two of the cards add up to 21, the player loses. Use pigeonhole principle to show ...
1
vote
1answer
89 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 ...
0
votes
3answers
70 views

Pigeonhole Principle and Equivalence Classes

Let $A$ be a finite set with $n \geq 4$ elements and let $\rho$ be an equivalence relation on $A$. Suppose that there are exactly four equivalence classes: $C_1, C_2, C_3, C_4$. Moreover we know that ...
4
votes
1answer
257 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 ...
2
votes
3answers
208 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. ...
4
votes
1answer
131 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?
2
votes
0answers
69 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 ...
6
votes
4answers
113 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 ...
2
votes
2answers
125 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 ...
2
votes
4answers
149 views

Pigeonhole principle for dominoes.

Suppose we have 13 dominoes, each with a red and blue integer number. Prove that there is a subset of 4 dominoes such that the sum of the 4 red numbers and the sum of the 4 blue numbers are both ...
1
vote
1answer
61 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
59 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 ...
2
votes
2answers
46 views

$2^n$ modulo n where n is odd always yields either an even or $1$

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or ...
0
votes
2answers
41 views

pigeonhole principle For 1-1 and onto function

$|A|=|B|=n\in N$ Prove/Disprove that if $f:A \rightarrow B$ is 1-1 then $f:A \rightarrow B$ is onto. The answer I saw used the Pigeonhole Principle, I am trying to prove it without the principle. ...
2
votes
3answers
207 views

Pigeonhole Principle -

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. Show that the number \begin{equation}x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))\end{equation} is even. I don't understand ...
0
votes
1answer
77 views

Proving something using Pigeonhole Principle [duplicate]

How do I prove the following using the Pigeonhole principle? Let $n$ be an odd integer. Prove that there exists a positive integer $k$ such that $2^k \mod n = 1$. I don't understand how I can prove ...
4
votes
1answer
133 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 ...
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 ...
1
vote
2answers
1k 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
1answer
60 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
65 views

Combinatorial Question using ramsey's theory or pigeonhole principle??

We are currently going over pigeonhole principle, ramsey's theorem (graphs and such). Stuck on this particular question: Within a group of an odd number of people, show that at least one person knows ...
0
votes
3answers
52 views

What Does “less than or equal to 1 apart” Mean?

I thought this question was classified as a word-meaning question. So, does "1 apart" mean 1/2 the side of the triangle? reference:
2
votes
1answer
247 views

Proving the Chinese Remainder Theorem using the Pigeonhole Principle

I am trying to prove a version of the Chinese Remainder Thoerem using the pigeonhole principle. The theorem that was provided: If n and m are relatively prime, then for all integers 0 ≤ a < n ...
2
votes
1answer
49 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 ...
1
vote
2answers
211 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
1answer
65 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
41 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 ...
2
votes
1answer
51 views

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color

Prove that in each coloring of a $4\times7$ board in two colors there's a square that all four of it's corners are colored by the same color. This is a pigeon hole principle question and I have a ...
1
vote
1answer
121 views

Pigeonhole Principle Discrete Math

At a dinner party there are 8 guests. The dinner takes place a table shaped like a regular octagon. Each edge has a place setting labeled with the name of a different guest. Originally each person ...
1
vote
1answer
52 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 ...
2
votes
1answer
79 views

Help with a pigeonhole principle?

Let $n \geq 1$ be an integer. Use the Pigeonhole Principle to prove that in any set of $n + 1$ integers from $\{1, 2, . . . , 2n\}$, there are two integers that are consecutive (i.e., di ffer by ...
0
votes
2answers
45 views

Couple of Counting (how many ways) questions.

1.If I have a group of 10 seats reserved for people, and there are n=>10 total people, how many ways are there to choose who gets the 10 seats? for ex:If there was a definite number of people lets ...
5
votes
4answers
155 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. ...
1
vote
1answer
44 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 ...
0
votes
3answers
80 views

Pigeonhole Principle about division

Prove that, for any $n+1$ integers $a_{1},a_{2},....,a_{n+1}$, there exist two of the integers $a_{i}$ and $a_{j}$ with $i \neq j$, such that $a_{i} - a_{j}$ is divisible by $n$. Please help me about ...