# Recent questions tagged pigeonhole-principle

1
An alternative proof of Theorem $3$ based on the generalized pigeonhole principle is outlined in this exercise. The notation used is the same as that used in the proof in the text. Assume that $i_{k}\leq n\:\text{for}\: k = 1, 2,\dots ,n^{2} + 1.$ Use the ... $n + 1,$ then there must be a decreasing subsequence of this length.
2
Let $n_{1}, n_{2},\dots,n_{t}$ be positive integers. Show that if $n_{1} + n_{2} +\dots + n_{t} − t + 1$ objects are placed into $t$ boxes, then for some $i, i = 1, 2,\dots,t,$ the $i^{\text{th}}$ box contains at least $n_{i}$ objects.
3
Let $x$ be an irrational number. Show that for some positive integer $j$ not exceeding the positive integer $n,$ the absolute value of the difference between $j x$ and the nearest integer to $j x$ is less than $1/n.$
4
There are $51$ houses on a street. Each house has an address between $1000\: \text{and}\: 1099,$ inclusive. Show that at least two houses have addresses that are consecutive integers.
5
Show that if $f$ is a function from $S\: \text{to}\: T,$ where $S\: \text{and}\: T$ are nonempty finite sets and $m = \left \lceil \mid S \mid / \mid T \mid \right \rceil ,$ then there are at least $m$ elements of $S$ mapped to the same value of $T.$ That is, show that there are distinct elements $s_{1}, s_{2},\dots,s_{m}\: \text{of}\: S$ such that $f (s_{1}) = f (s_{2}) =\dots = f (s_{m}).$
6
Is the statement in question $41$ true if $24$ is replaced by $2?$ $23?$ $25?$ $30?$
7
An arm wrestler is the champion for a period of $75$ hours. (Here, by an hour, we mean a period starting from an exact hour, such as $1\: \text{p.m.,}$ until the next hour.) The arm wrestler had at least one match an hour, but no more than $125$ total matches. Show that there is a period of consecutive hours during which the arm wrestler had exactly $24$ matches.
8
Prove that at a party where there are at least two people, there are two people who know the same number of other people there.
9
Find the least number of cables required to connect $100$ computers to $20$ printers to guarantee that $2$ every subset of $20$computers can directly access $20$ different printers. (Here, the assumptions about cables and computers are the same as in Example $9.$) Justify your answer.
10
Find the least number of cables required to connect eight computers to four printers to guarantee that for every choice of four of the eight computers, these four computers can directly access four different printers. Justify your answer.
11
A computer network consists of six computers. Each computer is directly connected to zero or more of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers. [Hint: It is impossible to have a computer linked to none of the others and a computer linked to all the others.]
12
A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.
13
There are $38$ different time periods during which classes at a university can be scheduled. If there are $677$ different classes, how many different rooms will be needed?
14
Assuming that no one has more than $1,000,000$ hairs on the head of any person and that the population of New York City was $8,008,278\:\text{in}\: 2010,$ show there had to be at least nine people in NewYork City in $2010$ with the same number of hairs on their heads.
15
In the $17^{\text{th}}$ century, there were more than $800,000$ inhabitants of Paris. At the time, it was believed that no one had more than $200,000$ hairs on their head. Assuming these numbers are correct and that everyone has at least one hair ... generalized pigeonhole principle to show that there had to be at least five Parisians at that time with the same number of hairs on their heads.
16
Show that if there are $100,000,000$ wage earners in the United States who earn less than $1,000,000$ dollars (but at least a penny), then there are two who earned exactly the same amount of money, to the penny, last year.
17
Show that there are at least six people in California (population: $37$ million) with the same three initials who were born on the same day of the year (but not necessarily in the same year). Assume that everyone has three initials.
18
Show that if $m$ and $n$ are integers with $m \geq 2 \:\text{and}\: n \geq 2,$ then the Ramsey numbers $R(m, n)\:\text{and}\: R(n, m)$ are equal. $\text{(Recall that Ramsey numbers were discussed after Example}\: 13\: \text{in Section}\: 6.2.)$
19
Show that if $n$ is an integer with $n \geq 2,$ then the Ramsey number $R(2, n)$ equals $n.\text{(Recall that Ramsey numbers were discussed after Example}\: 13\:\text{in Section}\: 6.2.)$
20
Use question $27$ to show that among any group of $20$ people (where any two people are either friends or enemies), there are either four mutual friends or four mutual enemies.
21
Show that in a group of $10$ people (where any two people are either friends or enemies), there are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four mutual friends.
22
Show that in a group of five people (where any two people are either friends or enemies), there are not necessarily three mutual friends or three mutual enemies.
23
Describe an algorithm in pseudocode for producing the largest increasing or decreasing subsequence of a sequence of distinct integers.
24
Suppose that $21$ girls and $21$ boys enter a mathematics competition. Furthermore, suppose that each entrant solves at most six questions, and for every boy-girl pair, there is at least one question that they both solved. Show that there is a question that was solved by at least three girls and at least three boys.
25
Show that whenever $25$ girls and $25$ boys are seated around a circular table there is always a person both of whose neighbors are boys.
26
Show that if there are $101$ people of different heights standing in a line, it is possible to find $11$ people in the order they are standing in the line with heights that are either increasing or decreasing.
Construct a sequence of $16$ positive integers that has no increasing or decreasing subsequence of five terms.
Find an increasing subsequence of maximal length and a decreasing subsequence of maximal length in the sequence $22, 5, 7, 2, 23, 10, 15, 21, 3, 17.$
Suppose that every student in a discrete mathematics class of $25$ students is a freshman, a sophomore, or a junior. Show that there are at least nine freshmen, at least nine sophomores, or at least nine juniors in the class. Show that there are either at least three freshmen, at least $19$ sophomores, or at least five juniors in the class