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
236
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
280
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
338
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
359
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
360
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
340
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
714
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
+
–
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.
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
320
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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.
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
276
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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.$
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
430
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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.
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
450
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 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
242
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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?$
Is the statement in question $41$ true if $24$ is replaced by$2?$$23?$$25?$$30?$
admin
284
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 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
275
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
1
votes
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.
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
481
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 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
369
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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.
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
477
views
admin
asked
Apr 29, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
pigeonhole-principle
descriptive
+
–
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.]
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
326
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 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
233
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