Tagged Questions

Questions involving the pigeonhole principle in Combinatorial Analysis.

1answer
201 views

Pigeonhole principle and sequences problem

Could you please tell me if this is the right approach to tackle this problem.I translated it from Spanish into English, so please excuse the wording and let me know if there's something that is not ...
3answers
134 views

Proof using pigeonhole and greatest integer (floor) function.

The question is to prove that if m is a positive integer then, $$[mx] = [x] + \left[x+\frac{1}{m}\right] +\left[x+\frac{2}{m}\right] + \cdots + \left[x+\frac{(m-1)}{m}\right]$$ for \$x \in ...
2answers
177 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 ...
10answers
4k views

100 Soldiers riddle

One of my friends found this riddle. There are 100 soldiers. 85 lose a left leg, 80 lose a right leg, 75 lose a left arm, 70 lose a right arm. What is the minimum number of soldiers losing all ...
1answer
165 views

If any x points are elected out of a unit square, then some two of them are no farther than how many units apart?

If 5 points are randomly positioned in a unit square, no two points can be greater than square root of 2 divided by 2 apart; divide up the unit square into four squares, and, based on the pigeonhole ...
1answer
486 views

Pigeonhole: Practical Applications in Computer Science

Most of the problems I've seen involving the pigeonhole principle have so far seemed fairly artificial. As I'm studying CompSci I'm interested what kind of practical, real world problems in CompSci ...
2answers
294 views

Pigeonhole: 12 numbers between 10 to 100 - 2 have a difference divisible by 11

Prove that given 12 numbers between 10 to 100 - 2 have a difference divisible by 11. I didn't understand the answer given in my lecture and thought that as usual I'd probably get a clearer answer ...
1answer
670 views

Combinatorics - pigeonhole principle question

This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition. An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a ...
2answers
232 views

How to recognize a pigeonhole problem?

I'm going to split this into 2 questions, the first I think might have an answer, the second may not. First, is there a general way to recognize a pigeonhole problem as such? I mean are there some ...
1answer
32 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}$ ...
2answers
480 views

Subsets with equal sums

I have a problem to solve but I am in need of your help. Subjects with equal sums: Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), ...
1answer
52 views

Possibility of constructing a desirable subset

Here is a question.I am quoting it: Question by user Nahum Litvin Let A be a set of 100 natural numbers. prove that there is a set B B⊆A such that the sum of B's elements can be divided by ...
2answers
211 views

regarding Pigeonhole principle

Let A be a set of 100 natural numbers. prove that there is a set B $$B\subseteq A$$ such that the sum of B's elements can be divided by 100 I am stuck for a few days now. Please help!
2answers
152 views

Pigeonhole principle problem

The problem I'm working on says: A basketball player has been training for 112 hours during 12 days. He has trained an integer number of hours every day. Prove that there was two consecutive days ...
1answer
203 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 ...
2answers
436 views

Some three consecutive numbers sum to at least $32$

Here's a question we got for homework: We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$. I assume we need the ...
2answers
159 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 ...
2answers
143 views

Bit strings (pigeonhole principle)

Here is how the question is posed: Let $s_1$, $s_2$, $s_3, \ldots, s_{90}$ be 90 bit strings of length nine or less. Prove that there exist two strings $s_i$ and $s_j$ with $i \neq j$ that contain ...
5answers
269 views

The Pigeon Hole Principle and the Finite Subgroup Test

I am currently reading this document and am stuck on Theorem 3.3 on page 11: Let $H$ be a nonempty finite subset of a group $G$. Then $H$ is a subgroup of $G$ if $H$ is closed under the ...
1answer
188 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
19answers
2k views

What is your favorite application of the Pigeonhole Principle?

The pigeonhole principle states that if $n$ items are put into $m$ "pigeonholes" with $n > m$, then at least one pigeonhole must contain more than one item. I'd like to see your favorite ...
1answer
113 views

Pigeonhole Principle used for Finding Numbers

I’m doing a review exercise that gives me the list of numbers from 100 to 1000. I need to find the number of different numbers that have a 0. I suppose I could do this with the Pigeonhole principle, ...
2answers
281 views

Maximum number of mutually orthogonal latin square pairs (definition provided)

An $n\times n$ matrix is defined to be a "latin square" if each row and column is a permutation of the first $n$ natural numbers. Two squares of same order are orthogonal if the $n^2$ pairs ...
2answers
1k views

In a group of 6 people either we have 3 mutual friends or 3 mutual enemies. In a room of n people?

A group of 6 people each pair is either a friend (acquaintance) or an enemy (stranger). It is to be proven that there are either 3 mutual friends or 3 mutual enemies in this group. I have an ad-hoc ...
4answers
332 views

Prove that 2 students live exactly five houses apart if

There are 50 houses along one side of a street. A survey shows that 26 of these houses have students living in them. Prove that there are two students who live EXACTLY five houses apart on the street. ...
4answers
433 views

Another pigeonhole principle question

Have another question for you today: A course has seven elective topics, and students must complete exactly three of them in order to pass the course. If 200 students passed the course, show that at ...
2answers
156 views

using pigeonhole principle for a hand of thirteen cards

Say I shuffle and deal a hand of thirteen cards. How can I apply the pigeonhole principle in these cases: The hand has at least four cards in the same suit The hand has at exactly four cards in some ...
2answers
189 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 ...
2answers
618 views

Chess Master Problem

From Introductory Combinatorics by Richard Brualdi We have a chess master. He has 11 weeks to prepare for a competition so he decides that he will practice everyday by playing at least 1 game a day. ...
1answer
317 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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.946187436580658, "perplexity_flag": "head"}