Dark Mode

Recent questions tagged pigeonhole-principle

0 votes

0 answers

1

Ace Academy Test Series Qn#7
A hash function h maps 16-bit inputs to 8 bit hash values. What is the largest k such that in any set of 1000 inputs, there are atleast k inputs that h maps to the same hash value? 3 4 10 64

Souvik33 asked in DS Oct 30, 2022

134 views

0 votes

0 answers

2

Ace Academy Test Series
A hash function h maps 16-bit inputs to 8 bit hash values. What is the largest k such that in any set of 1000 inputs, there are atleast k inputs that h maps to the same hash value? 3 4 10 64

Souvik33 asked in DS Oct 30, 2022

72 views

0 votes

1 answer

3

GATE ACADEMY TEST SERIES
What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state?

LRU asked in Mathematical Logic Sep 26, 2021

by LRU

354 views

1 vote

1 answer

4

TIFR CSE 2021 | Part A | Question: 1
A box contains $5$ red marbles, $8$ green marbles, $11$ blue marbles, and $15$ yellow marbles. We draw marbles uniformly at random without replacement from the box. What is the minimum number of marbles to be drawn to ensure that out of the marbles drawn, at least $7$ are of the same colour? $7$ $8$ $23$ $24$ $39$

soujanyareddy13 asked in Combinatory Mar 25, 2021

by soujanyareddy13

693 views

0 votes

0 answers

5

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

212 views

0 votes

0 answers

6

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

156 views

0 votes

1 answer

7

Kenneth Rosen Edition 7 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.$

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

206 views

0 votes

0 answers

8

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

262 views

0 votes

0 answers

9

Kenneth Rosen Edition 7 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}).$

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

143 views

0 votes

0 answers

10

Kenneth Rosen Edition 7 Exercise 6.2 Question 42 (Page No. 406)
Is the statement in question $41$ true if $24$ is replaced by $2?$ $23?$ $25?$ $30?$

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

151 views

0 votes

0 answers

11

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

161 views

0 votes

1 answer

12

Kenneth Rosen Edition 7 Exercise 6.2 Question 40 (Page No. 406)
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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

260 views

0 votes

0 answers

13

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

183 views

0 votes

1 answer

14

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

324 views

0 votes

0 answers

15

Kenneth Rosen Edition 7 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 ... is impossible to have a computer linked to none of the others and a computer linked to all the others.]

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

168 views

0 votes

0 answers

16

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

114 views

0 votes

0 answers

17

Kenneth Rosen Edition 7 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?

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

225 views

0 votes

0 answers

18

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

139 views

0 votes

0 answers

19

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

225 views

0 votes

0 answers

20

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

100 views

0 votes

0 answers

21

Kenneth Rosen Edition 7 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.

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

97 views

0 votes

0 answers

22

Kenneth Rosen Edition 7 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.)$

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

120 views

0 votes

0 answers

23

Kenneth Rosen Edition 7 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.)$

Lakshman Patel RJIT asked in Combinatory Apr 29, 2020

by Lakshman Patel RJIT

95 views

Page:

1
2
3
4
next »

Recent questions tagged pigeonhole-principle