search
Log In

Recent questions tagged pigeonhole-principle

0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
3
0 votes
0 answers
4
0 votes
0 answers
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}).$
asked Apr 29 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 13 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
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.]
asked Apr 29 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 7 views
0 votes
0 answers
13
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 13 views
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 11 views
0 votes
0 answers
16
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
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.)$
asked Apr 29 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
19
0 votes
0 answers
20
0 votes
0 answers
21
0 votes
0 answers
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 11 views
0 votes
1 answer
26
0 votes
1 answer
29
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
asked Apr 29 in Combinatory Lakshman Patel RJIT 16 views
...