Dark Mode

Recent questions tagged pigeonhole-principle

0 votes

0 answers

1

Show that if f is a function from S to T , where S and T are finite sets with |S| > |T|, then there are elements s1 and s2 in S such that f(s1) = f(s2), or in other words, f is not one-to-one. (Using the Pigeonhole Principle)

sadman_e asked in Mathematical Logic Aug 21, 2023

214 views

0 votes

0 answers

2

Kenneth Rosen, exercise: 6.2, question: 8
Show that if f is a function from S to T , where S and T are finite sets with |S| > |T |, then there are elements s1 and s2 in S such that f (s1) = f (s2), or in other words, f is not one-to-one. How can I prove it by using “proof by contradiction”? Is it possible to prove the same by using “proof by contraposition”? If yes, how?

Pineapple asked in Combinatory Mar 23, 2023

263 views

1 vote

0 answers

3

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

397 views

0 votes

0 answers

4

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

323 views

4 votes

1 answer

5

GO Classes Test Series 2024 | Discrete Mathematics | Test 4 | Question: 19
Let $\text{S} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}.$ What is the possible value of integer $\text{K}$ such that any subset of $\text{S}$ of size $\text{K}$ contains two disjoint subsets of size two, $\{x_{1}, x_{2}\}$ and $\{y_{1}, y_{2}\},$ such that $x_{1} + x_{2} = y_{1} + y_{2} = 9?$ $8$ $6$ $7$ $5$

GO Classes asked in Combinatory May 3, 2022

348 views

5 votes

1 answer

6

GO Classes Test Series 2024 | Discrete Mathematics | Test 4 | Question: 20
There are $k$ people in a room, each person picks a day of the year to get a free dinner at a fancy restaurant. $k$ is such that there must be at least one group of six people who select the same day. What is the possible value of such $k$ if the year is a leap year $(366$ days)? $1465$ $1831$ $1830$ $2197$

GO Classes asked in Combinatory May 3, 2022

347 views

3 votes

2 answers

7

GO Classes Test Series 2024 | Discrete Mathematics | Test 4 | Question: 21
Let $\text{S} = \{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21\}.$ What is the possible value of integer $\text{N} > 0$ such that for any set of $\text{N}$ integers, chosen from $\text{S},$ there must be two distinct integers such that one of them divides the other? $10$ $7$ $9$ $8$

GO Classes asked in Combinatory May 3, 2022

342 views

0 votes

1 answer

8

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

680 views

1 vote

1 answer

9

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

1.1k views

0 votes

0 answers

10

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.

admin asked in Combinatory Apr 29, 2020

by admin

316 views

0 votes

0 answers

11

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.

admin asked in Combinatory Apr 29, 2020

by admin

270 views

0 votes

1 answer

12

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

admin asked in Combinatory Apr 29, 2020

by admin

396 views

0 votes

0 answers

13

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.

admin asked in Combinatory Apr 29, 2020

by admin

436 views

0 votes

0 answers

14

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

admin asked in Combinatory Apr 29, 2020

by admin

238 views

0 votes

0 answers

15

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?$

admin asked in Combinatory Apr 29, 2020

by admin

266 views

0 votes

0 answers

16

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.

admin asked in Combinatory Apr 29, 2020

by admin

271 views

1 vote

1 answer

17

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.

admin asked in Combinatory Apr 29, 2020

by admin

448 views

0 votes

0 answers

18

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.

admin asked in Combinatory Apr 29, 2020

by admin

362 views

0 votes

1 answer

19

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.

admin asked in Combinatory Apr 29, 2020

by admin

453 views

0 votes

0 answers

20

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

admin asked in Combinatory Apr 29, 2020

by admin

305 views

0 votes

0 answers

21

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.

admin asked in Combinatory Apr 29, 2020

by admin

222 views

Page:

1
2
3
4
next »

Recent questions tagged pigeonhole-principle