# 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.

98 views

### Qn on Pigeon-Hole Principle

Let S be a set of 10 positive integers ≤ 50. Show that there two different (but not necessarily disjoint) subsets of four integers such that the sums of the 4 integers in the sets are equal. Having ...
163 views

### Pigeonhole principle problem involving circle and its chords

Several chords are drawn in a circle of radius 1 such that each diameter intersects no more than 4 of them. Prove that the sum of their lengths does not exceed 13.
87 views

### Prove that for positive number, some multiple only has 0 and d as it's digits

Let $n$ be a positive integer, and let $1<=d<=9$. Show that some multiple of $n$ has $0$ and $d$ as its only digits. I don't know how to even start this question. It's under the pigeonhole ...
251 views

### Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
75 views

### Prove that there exists a numbered socket such that for every orientation, two equal numbers coincide

There is a socket which has $6$ holes on the vertices of a regular hexagon. These holes are numbered $1, 2, \dots , 6$. Prove that there exists such a plug with $6$ prongs numbered such that no matter ...
64 views

### Smallest subset of $\{1,2,…,4n\}$ with a certain property

Fact 1: Let $A\subseteq\{1,2,...,2n\}$. If $n+1\leq |A|$, then there exists 2 elements $a,b\in A$ such that $a+b=2n+1$. Proof: This can be shown by writing $\{1,2,...,2n\}$ as the union of $n$ ...
41 views

### 7 points on a closed disk, one must be the center

I am trying a pigeonhole strategy for proving this assertion of a MO test: "Given 7 points on a closed disk of radius 1 such that the distance between any two of this points is at least one, then one ...
120 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 ...
144 views

116 views

### pigeonhole principle on a circle

In a disk of radius 10, how can we find all values n such that there are exactly n points in the disk and such that no matter how the n points are arranged, we can draw a disk with radius 1 in the ...
108 views

### Milk bottles and pigeonhole. [duplicate]

Possible Duplicate: Chess Master Problem A child drinks at least 1 bottle of milk a day. Given that he has drunk 700 bottles of milk in a year of 365 days, prove that for he has drunk exactly ...
320 views

### How the cardinality of $\mathbb{R^+}$ and $\mathbb{R}$ same?

Let me first confirm you that this question is not a duplicate of either this, this or this or any other similar looking problem. Here in the current problem I'm asking to disprove me(most probably ...
225 views

### geometric problem solved with Pigeon Hole Principle

The problem is: Show that among any 5 points in a equilateral triangle of unit side length, there are 2 whose distance is at most 1/2 units apart.
220 views

### A pigeonhole problem from “Conjecture and Proof”

I don't really know how to start this problem at all. I would like a solution or even hints. "Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$" The chapter in ...
153 views

### One of $2^1-1,2^2-1,…,2^n-1$ is divisible by $n$ for odd $n$

Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$. I know that pigeonhole principle would be helpful, but how should I apply it? ...
570 views

### Choose 38 different natural numbers less than 1000, Prove among these there exists at least two whose difference is at most 26.

Choose any 38 different natural numbers less than 1000. Prove that among the selected numbers there exists at least two whose difference is at most 26. I think I need to use pigeon hole principle, ...
301 views

492 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 ...
51 views

### Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$. My approach: Let $a_1,a_2,a_3,\ldots,a_{2^{n+1}-1}$ ...
53 views

### How can we prove that every sequence of $30$ elements from a set of three repeats a subsequence of length 3?

How can we prove that for every series over $30$ elements(included $30$), there must be a "sub" three element series then will repeat itself? (Series's numbers are only $\{1,2,3\}$) Example for a "...
60 views

### existence of a lattice rectangle in a $13 \times 13$ grid

Problem: Prove that if 53 points are chosen from a $13\times 13$ grid then there will necessarily exist a rectangle whose vertices are among the 53 points chosen. My try: I am guessing we have to ...
69 views

### $5$ points on a sphere [duplicate]

Diffuse $5$ points on a sphere. Prove there is a closed half-sphere that has at least $4$ points on it.
158 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.
865 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 two ...
1k 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 ...
277 views

### Pigeonhole Principle -

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. Show that the number $$x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))$$ is even. I don't understand ...
411 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 ...
2k 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, ...
243 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$, ...
56 views

### Are Square and equilateral triangle the only convex regular ngons that can be composed to smaller versions of themselves?

While I was trying to make an analogous question to Select $n^2 + 1$ points in the unit square. Show that at least two points are no more than a distance $\frac{\sqrt{2}}{n}$ apart, using equilateral ...
95 views

### Candidates in an exam

443 candidates enter the exam hall. There are 20 rows of seats I'm the hall. Each row has 25 seats. At least how many rows have an equal number of candidates. My attempt Seat 25 in the first row 24 ...
204 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, ...
170 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 ...
203 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...
217 views

### Twenty distinct integers are chosen from {1,2,…,69} and their differences

Twenty distinct integers are chosen from {1,2,...,69}. Prove that amongst their pairwise differences there are at least four which are identical. I understand that the set {1...69} is arbitrary. ...