Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
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
231
views
sadman_e
asked
Aug 21, 2023
Mathematical Logic
pigeonhole-principle
+
–
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?
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 wor...
Pineapple
275
views
Pineapple
asked
Mar 23, 2023
Combinatory
discrete-mathematics
kenneth-rosen
pigeonhole-principle
+
–
1
votes
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
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 h...
Souvik33
405
views
Souvik33
asked
Oct 30, 2022
DS
ace-test-series
data-structures
hashing
pigeonhole-principle
discrete-mathematics
+
–
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
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 h...
Souvik33
335
views
Souvik33
asked
Oct 30, 2022
DS
ace-test-series
data-structures
hashing
pigeonhole-principle
discrete-mathematics
+
–
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$
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 dis...
GO Classes
355
views
GO Classes
asked
May 3, 2022
Combinatory
goclasses2024-dm-4-weekly-quiz
goclasses
combinatory
pigeonhole-principle
multiple-selects
2-marks
+
–
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$
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 p...
GO Classes
349
views
GO Classes
asked
May 3, 2022
Combinatory
goclasses2024-dm-4-weekly-quiz
goclasses
combinatory
pigeonhole-principle
multiple-selects
2-marks
+
–
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$
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 ...
GO Classes
336
views
GO Classes
asked
May 3, 2022
Combinatory
goclasses2024-dm-4-weekly-quiz
goclasses
combinatory
pigeonhole-principle
multiple-selects
2-marks
+
–
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?
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 co...
LRU
703
views
LRU
asked
Sep 26, 2021
Mathematical Logic
pigeonhole-principle
discrete-mathematics
test-series
+
–
1
votes
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$
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 ...
soujanyareddy13
1.1k
views
soujanyareddy13
asked
Mar 25, 2021
Combinatory
tifr2021
combinatory
pigeonhole-principle
+
–
8
votes
1
answer
10
GATE Overflow Test Series | Mock GATE | Test 1 | Question: 25
The minimum number of integers to be selected from the set $S = \{1, 2, \dots , 9\}$ so that the difference of at least two of the integers is guaranteed to be $5$ is ___________ $4$ $5$ $6$ $7$
The minimum number of integers to be selected from the set $S = \{1, 2, \dots , 9\}$ so that the difference of at least two of the integers is guaranteed to be $5$ is ___...
gatecse
735
views
gatecse
asked
Jan 3, 2021
Combinatory
go2025-mockgate-1
pigeonhole-principle
combinatory
+
–
2
votes
1
answer
11
GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 1
The minimum number of people that must be in a room to ensure that at least three were born on the same day of the week is $\_\_\_\_\_$
The minimum number of people that must be in a room to ensure that at least three were born on the same day of the week is $\_\_\_\_\_$
gatecse
222
views
gatecse
asked
Jun 28, 2020
Combinatory
go2025-dm-2
counting
combinatory
pigeonhole-principle
easy
numerical-answers
+
–
5
votes
1
answer
12
GATE Overflow Test Series | Discrete Mathematics | Test 2 | Question: 9
$15$ students took a quiz of $15$ questions where each question carry $1$ mark with no negative markings for wrong answer. The sum of their scores came out to be $100.$ Now consider the following two statements $S_1:$ All the ... true Only Statement $S_2$ is true Both $S_1$ and $S_2$ can be true Both $S_1$ and $S_2$ are false
$15$ students took a quiz of $15$ questions where each question carry $1$ mark with no negative markings for wrong answer. The sum of their scores came out to be $100.$ N...
gatecse
311
views
gatecse
asked
Jun 28, 2020
Combinatory
go2025-dm-2
pigeonhole-principle
counting
combinatory
+
–
0
votes
0
answers
13
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.
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...
admin
317
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
14
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.
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,\...
admin
272
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
1
answer
15
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.$
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 th...
admin
423
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
16
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.
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 consecut...
admin
446
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
17
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}).$
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 \r...
admin
240
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
18
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?$
Is the statement in question $41$ true if $24$ is replaced by$2?$$23?$$25?$$30?$
admin
281
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
19
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.
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 hou...
admin
274
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
1
votes
1
answer
20
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.
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
473
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
21
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.
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$ differe...
admin
365
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
1
answer
22
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.
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 compute...
admin
470
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
23
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.]
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 th...
admin
318
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
0
votes
0
answers
24
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.
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 th...
admin
230
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
Page:
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register