# Tagged Questions

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

209 views

### Problem on pigeon hole principle

This is a problem based on pigeon hole principle. A tennis player has three weeks to prepare for a tennis tournament.She decides to play at least one set every day but not more than 36 in all.Show ...
93 views

### Logic Questions with Pigeonhole Principle

"If $n$ objects are distributed into $k$ boxes, then at least one box must contain at least _____ objects." Fill in the blank How many people must we have in a room to ensure that six of them were ...
276 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 ...
87 views

### Pigeonhole proof of the existence of two numbers with given sum [duplicate]

Let $|W|=m+1$ and $W$ be a subset of $X=\{1,2,3,\dots ,2m\}$ ($m$ is any natural number). Prove there exists two numbers in $W$ whose sum is $2m+1$. Can anyone give me a hint to prove this? I ...
104 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 ...
84 views

### Pigeonhole principle question - relatively prime

Prove that every subset A of the set {2, 3, ... 99, 100} with |A| > 26, has at least one pair of integers that is not relatively prime. 2, 3, 5 .. , there are 26 primes below 100. Can someone give ...
366 views

### Constructive proof of pigeonhole principle

I'm trying to prove Pigeonhole principle with Coq proof assistant. Here is how I defined it: ...
113 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.
283 views

### How many subsets of $\{1, 2, …, n\}$ contain $1$ and how many don't? [closed]

Consider the set $A = \{1, 2, …, n\}$ (a) How many subsets of A contain $1$? I got $2^n - 2^{n-1}$ (b) How many subsets of A do not contain $1$? I got $2^{n-1}$ (c) Use the pigeonhole principle ...
85 views

### Prove if n<m there is at least one [(n/m)]?

Suppose there are n programmers in m cubicles. Prove that there must be at least one cubicle containing at least $\lceil \frac{n}{m} \rceil$ programmers. Note: I was not able to find the right sign [ ...
79 views

### Number theoretical Application of the Pigeonhole Principle

I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle". ...
78 views

### On a strange pigeonhole principle problem

Given distinct integers $a_1, a_2, \cdots, a_{63}$. Prove that there exists $a_i, a_j, a_m, a_n$ such that $(a_i - a_j)(a_m - a_n)$ is divisible by $1984$. I have no idea of how to create the ...
96 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 ...
1k views

### General Pigeonhole Principle - Coin Flips

I am trying to solve a problem using the general Pigeonhole Principle. The problem statement is as follows: A coin is flipped three times and the outcomes recorded. So, HTT might be recorded ...
55 views

### 123 persons in a cafe, and pigeons and boxes

$123$ persons are in a cafe. The sum of their ages is $3813$. Is it always possible to find $100$ among them so that their total age is greater or equal to $3100$? Looks like ...
39 views

### Regarding Thue's congruence theorem.

Did the mathematician Thue have a theorem where if $X\cdot N$ is congruent to $y \pmod m$, gcd$(y'm)=1$ then $1 \lt X \le \sqrt{m}$, or $1 \lt Y \le \sqrt{m}$? I'm not sure if I saw this in a number ...
185 views

### Select 100 integers from 1,2,…,200 [duplicate]

Prove that if 100 integers are chosen from 1,2,...,200, and one of the integers chosen is less than 16, then there are two chosen numbers such that one of them is divisible by the other. Thanks in ...
48 views

### four point in a row

We have painted all dots of page with two colors(blue and green), proof that there are four point with green color in a line that distance of any two neighbors of this four is one unit or there are ...
38 views

77 views

### 10 non-increasing or non-decreasing sequence from 101 random numbers [duplicate]

In $101$ random integer numbers $a[i],i=0, \cdots,100$, prove that we can always find $10$ non-increasing or non-decreasing sequence. A sequence is a sequence of numbers is an array of numbers ...
138 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 ...
76 views

### Pigeon Hole Principle in Unit Disk [duplicate]

Let $n$ be a natural number such that $n \ge 2$ and given complex number $z_1, z_2, \ldots, z_n$ that is contained in an open unit disk centered at origin. Prove that there exists $\epsilon_l = \pm 1$ ...
50 views

### Divisibility combinatorics

Let $A$ be a set of $1008$ positive integers bounded above by $2014$. It is then said that there must be two integers in $A$ such that one divides the other but I can't immediately see how to prove ...
85 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. ...
252 views

### 10 points inside a square - minimum distance between any of them

A square of side 1 is given, and 10 points are inside the square. If we divide the square into 9 smaller squares, and apply Dirichlet principle, we can prove that there are 2 of these 10 points whose ...
47 views

### The Probabilistic Pigeon Hole Principle 2

(a) A group of 15 boys plucked a total of 100 apples. Prove that two of those boys plucked the same number of apples.
50 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 ...
355 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 ...
696 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 ...
825 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 ...
209 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 ...
84 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 ...
58 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 ...
136 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 ...
55 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 ...
117 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 ...
70 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$ ...
619 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 ...
71 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 ...
63 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 ...
576 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 ...
159 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 ...
108 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 ...
127 views

### If ten points are on a unit square, one pair is at most $\sqrt2/3$ apart

Ten points are placed in a unit square. Show that there is a pair of points at most $\sqrt2/3$ apart. I'm not sure how to proceed with this problem, and have not had any luck so far.
82 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 ...
106 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 ...
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 ...