Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pigeonhole-principle]

Questions involving the pigeonhole principle, which states that if $n$ items are placed in $m$ containers and $n>m$, then at least one container has more than one item.

1
vote
1answer
35 views

Show that the sum or difference of $a_i$ and $a_j$ from a set of seven distinct integers is divisible by 10

I know this is a duplicate of this question, but I don't understand the top answer at all. How does squaring $a$ show what we're supposed to show? Here's my intuition on how to prove this: $a_i$ and ...
1
vote
1answer
30 views

Deducing divisibility based on Pigeonhole Principle

I am trying to solve this below problem from Norman Bigg's Discrete Mathematics textbook, but cannot reconcile his solution with my work. Let $X$ be a subset of $\{1, 2, \ldots 2n\}$ and $Y$ be ...
0
votes
1answer
34 views

pigeon hole principle [arrangement] [duplicate]

There are G girl students and B boy students in a class that is about to graduate. You need to arrange them in a single row for the graduation. To give a better impression of diversity, you want to ...
1
vote
1answer
82 views

Dealing with Pigeonhole Principle Problems [closed]

Question: Eleven numbers are chosen from 1, 2, 3, ..., 99, 100. Show that there are two nonempty disjoint subsets of these eleven numbers whose elements have the same sum. Does anyone know how to ...
1
vote
0answers
31 views

Monochromatic triangle - graph coloring

I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a ...
0
votes
1answer
43 views

proof by letters with characters

An authentication system accepts passwords that are composed of lowercase letters from a to z and digits from 0 to 9. Prove that, in this system, given any set of 3000 passwords, there must be at ...
8
votes
1answer
67 views

On $\sup|\varphi^{-1}(n)|=+\infty$

I am trying to find an elementary proof of the following fact: Given some $N\geq 2$, there are $N$ distinct integers $a_1,\ldots,a_N$ such that $\varphi(a_1)=\ldots=\varphi(a_N)$ with $\varphi$ ...
0
votes
2answers
42 views

algorithm problem solving [closed]

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.
1
vote
1answer
38 views

$I$ is a union of intervals such that there do no exist 2 points in $I$ with difference $1/12$.Prove the sum of lengths of intervals is at most $1/2$

Consider $I$ a union of disjoint intervals inlcuded in the interval $[0, 1]$ such that there do no exist 2 points in $I$ situated at distance $1/12$. Prove that the sum of the lengths of the intervals ...
4
votes
5answers
270 views

Splitting a string into 2 parts such that the number of 1's in part A are equal to the number of 0's in part B.

The full question is as follows. Prove that every binary string of length $n$ can be split down into 2 substrings where string $S = A.B$ such that the number of $0's$ in A is equal to the number of $...
1
vote
1answer
102 views

Combinatorics: Prove that $x, y, z$ exist such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$

Suppose we have a subset of $2n-1$ numbers from the set ${1, 2, 3, ..., 2^n-2}$. Prove that there exits $x, y, z$ such that $\frac {1}{2} \leq \frac {x^2}{yz} \leq 2$ I'm fairly new to this topic, ...
1
vote
1answer
70 views

Bob selects four points on a $10\times 10$ square.

Bob selects four points on a $10\times 10$ square. Is it true that two of them are less than $\sqrt{101}$ units apart? I know how to prove things like this for five points. These seems ...
-1
votes
1answer
29 views

how to use the pigeon hole principle on a graph problem? [duplicate]

I have this given problem: In a class there is 6 students,every 2 students of 6 know each other in advance or they don't. Show that there is 3 students that don't know each other in advance or that ...
0
votes
0answers
31 views

A deck of cards and the Pigeonhole Principle

I am trying to solve the following problem: How many cards must be chosen from a standard deck of 52 cards to guarantee that there are at least two cards of each of two different kinds? It isn't ...
1
vote
1answer
29 views

Question on a proof of no existance of monochromatic triangle in any tricoloring of edges of $K_{16}$

Here is a question on the book "Problem -Solving Strategies" by Arthur Engel, with a provided solution: In the solution, they partitioned the abelian group into 3 sets such that none of them is sum-...
1
vote
1answer
56 views

Finding the minimum number of cards to be drawn Generalized Pigeonhole Principle

Suppose you have a drawer with cards on which a number $1$ through $18$ is written. You can pick cards from the drawer with your eyes closed. What is the minimum number of cards you have to draw to ...
2
votes
1answer
40 views

Pigeonholes and onto functions

I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is $3^5 - C(3, 2)2^5 + C(3, 1)1^5$ and not $3^5 - C(3, 2)2^5 - C(3, 1)1^5$ ...
-1
votes
2answers
76 views

Pigeonhole Principle Proof Generalized

An airport sees 1500 takeoffs per day. Prove that there are two planes that leave within a minute of each other. All I can get started with is finding the total minutes in a day- 1440min. I ...
7
votes
2answers
60 views

Difficult variation of the committee problem

It is a trivial exercise in the pigeonhole principle to show that if an organization contains $m$ people and forms disjoint committees of $n$ members each, then at most $$\bigg \lfloor \frac{m}{n} \...
0
votes
1answer
24 views

Pigeonhole Principle: Proof that in an isosceles triangle with both side lengths 2 amongst 5 random points within there's two with distance $d < 1$

We're tasked to prove using the pigeonhole principle that, given an isosceles triangle with the two equal side lengths being $l = 2$, you can always choose $5$ random points of which two will have a ...
0
votes
2answers
23 views

Pigeonholes problem help please

Let $L$ be a list (not necessarily in alphabetical order) of the 26 letters in the English alphabet (which consists of 5 vowels, and 21 consonants). a) Show that $L$ has a sublist consisting of ...
1
vote
1answer
33 views

Be A a group of sequences of length 9 made of {0,1} and its given that |A|=52. show that exists 2 sequences a1, a2 that belong

Question: Let $A$ be a group of sequences of length 9 made of $\{0,1\}$ and its given that $|A|=52$. Show that there exists 2 sequences $a_1$, $a_2$ that belong to $A$ so you could replace at most 2 ...
0
votes
1answer
33 views

Pigeonhole principle - cutting a square out of a rectangle

Paper sized 10cm x 100cm was filled with 999 points. Show that you can cut a 1cm x 1cm square out of the paper without touching any of the points. Can anyone help me understand this problem..I know ...
1
vote
1answer
53 views

Pigeonhole Principle Question - Selecting some items from a box that contains fifty items with different colors

Please help me understand this question. I got the answer 101, however it says the solution to this question is 11. Perhaps it was a typo? Suppose you select some items from a box that contains fifty ...
0
votes
2answers
33 views

How many people need to turn up to be sure of making at least one team?

So pigeonhole principle states when there are m objects to be divided into n sets then at least one contains r+1 objects. i.e m > nr In this question the m objects should be 12 months in 5 people so ...
1
vote
6answers
267 views

Pigeon hole principle: Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three. [closed]

Prove that any set of six positive integers whose sum is 13 must contain at least one subset whose sum is three. My work. I am trying by using the Pigeon hole principle. I have proved that at least ...
-1
votes
1answer
56 views

There is a space for a circle in a rectangle filled with squares

I placed 120 unit squares inside a $20\times 25$ rectangle. Prove that it is possible to place a circle with an unit diameter (with a diameter witj length 1), such that it doesn’t have a common point ...
2
votes
0answers
60 views

Generalized Birthday Problem? Combinatorics

I am having a difficult time understanding how to think about and analyze the following problem: (I have done research, but I am not sure how to phrase my enquiries and my research seems to be almost ...
1
vote
1answer
37 views

The pigeonhole principle - 30 pens in a drawer

I need help with the following task. It needs to be solved using the pigeonhole principle. There are 10 red, 8 blue, 8 purple and 4 yellow pens in a drawer. We pick them out, one by one, in the dark....
2
votes
2answers
180 views

Applying the Pigeonhole Principle to a Set of Subsets

Let $A$ be a set of six positive integers each of which is less than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum. This is what I've ...
0
votes
1answer
38 views

How to change proof by contradiction to pigeon hole principle?

Every point in a straight line are coloured using 2 colours. Show that there are 2 points and their midpoint (lying on this straight line) of the same colour. I saw this question on a pigeon hole ...
1
vote
1answer
59 views

Three sides of a regular triangle is bicolored, are there three points with the same color forming a rectangular triangle?

The sides of a regular triangle $\triangle_1=ABC$ is bicolored(red, and blue), Do there exist three vertices on the perimeter of $\triangle_1$ three monochromatic vertices forming the corners of a ...
1
vote
1answer
44 views

Show that distinct subsets of a specific-cardinality subset have equal sums

For $S\subset\{1,2,...,117\}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be ...
0
votes
1answer
66 views

Show that distinct subsets of a set have equal sums using pigeonhole principle

For $S\subset\{1,2,...,117\}$ and $|S|=10$, I need to show that distinct such subsets have equal sums. That is, if $s_A$ is the sum of the elements in one 10-cardinality subset and $s_B$ is the sum of ...
0
votes
0answers
48 views

Showing that a greatest common divisor must be 1 or 2 using pigeonhole principle

I need to prove that for any $S \subset \{1,2,...,2018\}$ with $|S|=673$, it follows that $\exists\,a,b \in S$ such that $gcd(a,b)<3$. I can see the obvious application of pigeonhole principle ...
0
votes
2answers
33 views

How many people have to be gathered to ensure at least 9 people have the same first letter of their first name?

I know I use generalized pigeon hole principle where $n/k= m$. I know $n$ is pigeons and $k$ is pigeonholes. I know I have to do n/#=m for this one. So its n/#=9. Im not sure what would be pigeonholes ...
0
votes
2answers
46 views

(Generalised) pigeonhole principle

Answer the following questions and justify your answer. Hint: Use the (generalised) pigeonhole principle. Given any set S of 6 natural numbers, must there be two numbers in S that have the same ...
0
votes
1answer
47 views

Proof using an application of Pigeonhole Principle

Prove that every $(n+1)$-element subset of $\{1,2,3,\dots,2n\}$ contains $2$ distinct integers $p$ and $q$, such that gcd$(p,q)=1$. Here's my attempt: Let $X \subseteq \{1,2,3,...,2n\}$ be the set ...
1
vote
1answer
39 views

decimal expansion of an integer

Can someone be so kind as to explain what is meant by the decimal expansion of an integer? I saw the following at this link but I don't know what decimal expansion of an integer refers to: https://...
4
votes
1answer
43 views

Color an infinite equilateral grid with seven colors. Can it be possible to prove using Pigeonhole Principle that a monochromatic triangle exists?

I found a problem on Brilliant, and wonder if it has a Pigeonhole solution. You have an infinite lattice of equilateral triangles and you would like to fill each node with one of seven colors. ...
-1
votes
1answer
22 views

Pigeon hole principle doubt [closed]

Question Of 12 distinct two digits numbers we can select 2 with a two digit difference of the form aa Can anyone please explain me what this question means
-1
votes
1answer
86 views

What mathematics cannot be reduced to pigeonhole?

Pigeonhole is a fundamental principle without which state of mathematics will be much different. However what examples of good mathematics has not yet been proved and cannot be proved with pigeonhole ...
3
votes
3answers
282 views

Pigeonhole Principle Issue five integers where their sum or difference is divisible by seven.

Given any five integers, there will be two that have a sum or difference divisible by 7. I'm trying to solve this using the Pigeonhole Principle, but it is not making sense to me, how this principle ...
6
votes
6answers
3k views

Prove that given any five integers, there will be three for which the sum of the squares of those integers is divisible by 3.

Basically the question is asking us to prove that given any integers $$x_1,x_2,x_3,x_4,x_5$$ Prove that 3 of the integers from the set above, suppose $$x_a,x_b,x_c$$ satisfy this equation: $$x_a^2 + ...
1
vote
2answers
22 views

G=(V,E) a graph that that maintains this condition $\left |E \right |\geq \left | V \right |\geq \left |3 \right |$ must have a circle

Condition : $\left |E \right |\geq \left | V \right |\geq \left |3 \right |$ and graph G=(V,E). I need to proove it without using any graph theorems and lemmas(if so then I have to proove them). I ...
1
vote
0answers
65 views

Approximating a real arbitrarily well by $Z$-linear combination of two reals having irrational ratio.

$\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\Z}{\mathbb Z}$ $\newcommand{\R}{\mathbf R}$ Let $\alpha$ and $\beta$ be positive real numbers such that $\alpha/\beta$ is irrational. Then the following ...
0
votes
0answers
16 views

Show that for each integer n, there is a multiple of n whose decimal expansion contains only 1s and 0s [duplicate]

That's an exercise my professor solved in class, but I forgot half of how he did it. He used the pigeonhole principle...
7
votes
3answers
3k views

A standard and rigorous proof using the pigeonhole principle

Now there is a question: For twenty two-digit numbers, we add two digits together. (like 12 and get the result 3) Prove in these twenty numbers, there must be at least 2 same results. Now I know I ...
0
votes
1answer
29 views

Splitting a set in two

The set {1, . . . , 9} is split in any way into two subsets. Prove that in at least one subset there are three numbers of which one is the arithmetic mean of the other two. I tried a lot on this ...
0
votes
1answer
436 views

Give a proof by contradiction to show if the odd integers $1,3,5,7,9,11,13,15,17,19,$ are placed around a circle…

Give a proof by contradiction to show that if the odd integers $1,3,5,7,9,11,13,15,17,19,$ are placed randomly around a circle (without repetition), then there must exist three adjacent numbers along ...