Questions involving the pigeonhole principle in Combinatorial Analysis.

learn more… | top users | synonyms

2
votes
2answers
235 views

The decimal expansion of the quotient of two integers

It is an exercise in a book on discrete mathematics.How to prove that in the decimal expansion of the quotient of two integers, eventually some block of digits repeats. For example: $\frac { 1 }{ 6 } ...
2
votes
1answer
451 views

Pigeonhole Principle on Graphs

I just have a last minute question for my combinatorics final (which is in one hour!!). My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole ...
2
votes
2answers
219 views

Question about the Pigeonhole Principle

The question is: Let $A = \{1,2,3,4,5,6,7,8\}$. If five integers are selected from $A$, must at least one pair of the integers have a sum of $9$? The book explains the solution by dividing the ...
2
votes
2answers
344 views

Pigeonhole principle question confusion

Now I understand it. I just learnt this principle. I am doing a problem in which there's a box with many red socks, green socks and blue socks. First question was how many minimum socks should I pick ...
2
votes
2answers
395 views

Selecting from $\{1,2,3,4,5,6,7,8,9\}$ to guarantee at least one pair adds to $10$

How many numbers must be selected from the set $\{1,2,3,4,5,6,7,8,9\}$ to guarantee that at least one pair of these numbers add up to $10$? Justify your answer. Here's my answer. Consider the ...
2
votes
3answers
218 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 ...
2
votes
1answer
183 views

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10

Show that any set of 7 distinct integers includes two integers $x$ and $y$, such that either $x-y$ or $x+y$ is divisible by 10. I'm trying to apply the pigeonhole principle, but haven't been able to ...
2
votes
2answers
100 views

Pigeonhole Principle Exercise

Show that any subset of $\{1, 2, 3, ..., 200\}$ having more than $100$ members must contain at least one pair of integers which add to $201$. I think it is doable using the Pigeonhole Principle.
2
votes
4answers
825 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, ...
2
votes
2answers
172 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$, ...
2
votes
2answers
80 views

Show that some 5 consecutive chairs must be occupied.

A group of 25 people are seated in a row of 30 chairs. Show that some 5 consecutive chairs must be occupied.
2
votes
1answer
257 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 ...
2
votes
2answers
96 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 ...
2
votes
1answer
111 views

Pigeonhole Principle / Number Theory

Let $S$ be a subset of $A=\{1,2,3,...,1000\}$. Find the largest number of elements in $S$ such that for any $a, b \in S$ with $a>b$, $a-b$ does not divide $a+b$. I've tried numerous approaches, ...
2
votes
2answers
121 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$ ...
2
votes
1answer
124 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 ...
2
votes
1answer
136 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 ...
2
votes
1answer
144 views

Using the Pigeonhole Principle to show that $2$ of any $n+1$ numbers from $\{1,2,\ldots,2n\}$ sum to $2n+1$

Let n be greater or to 1, and let S be an (n+1)-subset of [2n]. Prove that there exist two numbers in S whose sum is 2n+1. I know I have to use the pigeonhole principle - no idea how to start...
2
votes
2answers
31 views

Is this question a pigeon hole question?

How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15? Explain. It seems like this is similar to the birthday pigeon hole ...
2
votes
1answer
241 views

Pigeonhole Principle

Let $X = {x_0, x_1, · · · , x_m}$ be a subset of ${1, 2, · · · , n}$, where $m > n/2$, and $x_0$ is the smallest number in $X$. Use the pigeonhole principle to show that $X$ contains two numbers ...
2
votes
2answers
74 views

Any two points inside a circle are within a diameter of each other.

In many problems involving the Pigeonhole Principle, we often assume the following lemma: Lemma: The distance between any two points in a circle of radius $r$ is at most $2r$. Intuitively, this ...
2
votes
3answers
262 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. ...
2
votes
2answers
253 views

Extended Pigeonhole Principle: How to prove it?

A version of the pigeonhole principle is: (1) If m objects are put in n boxes and n < m, then at least one box contains at least ceil(m/n) objects An alternate (more generalized) version ...
2
votes
2answers
70 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 ...
2
votes
2answers
156 views

Pigeonhole-principle with two choices

I am able to solve this sort of problem pretty easily. An arm wrestler is the champion for a period of 75 hours. The arm wrestler had at least one match an hour, but no more than 125 total ...
2
votes
1answer
66 views

Room full of flies

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. This is from a math class, I couldn't devise an ...
2
votes
2answers
82 views

Chords of a 20-gon

Twenty points lie on a circle, so as to form a regular polygon. Then they are split into ten pairs, and the points in each pair are connected by a chord. Prove that some pair of these chords have the ...
2
votes
1answer
46 views

Seems straightforward pigeonhole

If we are given $37$ integers then show that it is possible to choose $7$ of them with sum divisible by $7$. I have tried this problem but with no avail. If we assume there are no integers with ...
2
votes
2answers
136 views

Prove two numbers of a set will evenly divide the other

We have a set A of numbers 1, 2, 3... to 200 The question is asking me to prove that if I choose 101 numbers from the set, there will be two such that one evenly divides the other. I know this ...
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 ...
2
votes
1answer
57 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 ...
2
votes
4answers
151 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 ...
2
votes
2answers
47 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 ...
2
votes
1answer
256 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
57 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 ...
2
votes
1answer
82 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 ...
2
votes
1answer
67 views

Small Combinatorical Question - Pigeonhole Principle Related

Suppose there are $77$ positive integers arranged in a row such that their sum is $140$. I want to show there is a sequence of adjacent integers in the row whose sum is $13$. My line of thought is ...
2
votes
1answer
92 views

pigeonhole principle with sequence of numbers

Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$. ...
2
votes
1answer
88 views

Application of pigeonhole principle

Select $11$ diff erent numbers from $f\{1,2,...,20\}$. Prove that two of your numbers, $a$ and $b$, will diff er by two. Clearly this is an application of the pigeonhole principle. However, I'm not ...
2
votes
1answer
132 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle
2
votes
1answer
217 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, ...
2
votes
1answer
122 views

A game involving points in the integer plane - who wins?

I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of ...
2
votes
1answer
123 views

A family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be linearly dependent

I was bored earlier and began to think of the pigeonhole principle, and it came to me that it could be used to show that a family of $n$ non-zero vectors of an $(n-1)$-dimensional vector space must be ...
2
votes
2answers
327 views

Pigeonhole Principle Points in a Triangle

Suppose we have an equilateral triangle with side length $1$. In this equilateral triangle, we place $8$ points either on the boundary or inside the triangle itself. Then what is the maximum possible ...
2
votes
1answer
272 views

Pigeonhole principle to prove division

Here's a little question that we were shown in class: Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$. Prove that there are two elements of $A$ such that one is a ...
2
votes
2answers
124 views

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n ...
2
votes
2answers
81 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 ...
2
votes
1answer
51 views

Average number of pigeon holes.

I'm an engineer not a mathematician, and I have a 3 part question that's applicable to a parallel computer system my team is designing. We have 10 CPU cores (ie - 10 pigeons) randomly reading from 10 ...
2
votes
1answer
223 views

pigeonhole principle 20 balls

I've worked out the answer to this as 13 since it's common sense, but we are supposed to apply the pigeon-hole principle, and I don't see how it is applicable here. A bowl contains 10 red balls ...
2
votes
0answers
20 views

Need a hint with permutations and pigeonhole-principle question

let $\pi_1,\pi_2,\pi_3\in S_{28}$. Help me prove that there are two sub-sequences of 28 with length 4 $i_1< i_2 <i_3<i_4,\ and\ \ j_1<j_2<j_3<j_4$ so that $\pi_q(i_n)=\pi_p(j_n)$ ...