menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions tagged pigeonhole-principle

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions tagged pigeonhole-principle

0 votes
0 answers
1
Kenneth Rosen Edition 7th Exercise 6.2 Question 47 (Page No. 407)
An alternative proof of Theorem $3$ ... there is no increasing subsequence of length $n + 1,$ then there must be a decreasing subsequence of this length.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 46 (Page No. 407)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 45 (Page No. 407)
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.$
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.$
asked Apr 29 in Combinatory Lakshman Patel RJIT 5 views
0 votes
0 answers
4
Kenneth Rosen Edition 7th Exercise 6.2 Question 44 (Page No. 406)
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.
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
5
Kenneth Rosen Edition 7th Exercise 6.2 Question 43 (Page No. 406)
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 ... $f (s_{1}) = f (s_{2}) =\dots = f (s_{m}).$
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 41 (Page No. 406)
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 ... than $125$ total matches. Show that there is a period of consecutive hours during which the arm wrestler had exactly $24$ matches.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 39 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 38 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 37 (Page No. 406)
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 ... impossible to have a computer linked to none of the others and a computer linked to all the others.]
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 36 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 35 (Page No. 406)
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?
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?
asked Apr 29 in Combinatory Lakshman Patel RJIT 6 views
0 votes
0 answers
14
Kenneth Rosen Edition 7th Exercise 6.2 Question 34 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 33 (Page No. 406)
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 ... to show that there had to be at least five Parisians at that time with the same number of hairs on their heads.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 32 (Page No. 406)
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.
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
17
Kenneth Rosen Edition 7th Exercise 6.2 Question 31 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 30 (Page No. 406)
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.)$
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 29 (Page No. 406)
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.)$
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.)$
asked Apr 29 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
20
Kenneth Rosen Edition 7th Exercise 6.2 Question 28 (Page No. 406)
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.
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 6 views
0 votes
0 answers
21
Kenneth Rosen Edition 7th Exercise 6.2 Question 27 (Page No. 406)
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.
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
24
Kenneth Rosen Edition 7th Exercise 6.2 Question 24 (Page No. 406)
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.
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
Kenneth Rosen Edition 7th Exercise 6.2 Question 22 (Page No. 406)
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.
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.
asked Apr 29 in Combinatory Lakshman Patel RJIT 14 views
0 votes
1 answer
29
Kenneth Rosen Edition 7th Exercise 6.2 Question 19 (Page No. 405 - 406)
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 ... there are either at least three freshmen, at least $19$ sophomores, or at least five juniors in the class
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
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...