COMP2121A: Discrete Mathematics
Homework 2 Due Date: Nov 8, 2022
Rules: Discussion of the problems is permitted, but writing the assignment together is not
(i.e. you are not allowed to see the actual pages of another student).
Course Outcomes
• [O1. Abstract Concepts]
• [O2. Proof Techniques]
• [O3. Basic Analysis Techniques]
Hint: You may write programs for some counting questions.
1. (10 points) [O1, O3] Let X = {x1, x2, ..., xm} and Y = {y1, y2, ..., yn}.
(a) How many different relations are there over X and Y ? (The relation defined on
two sets is a subset of their Cartesian product. Mathematically, the Cartesian
product of set A and B denoted by A×B is equal to {(a, b)|a ∈ A and b ∈ B}.)
(b) How many different functions are there from X to Y ?
(c) What is the condition m and n should satisfy to make injective functions exist?
What is the number of injective functions under the condition (in terms of m
and n)?
(d) What is the condition m and n should satisfy to make surjective functions exist?
What is the number of surjective functions under the condition (in terms of m
and n)?
(e) What is the condition m and n should satisfy to make bijective functions exist?
What is the number of bijective functions under the condition (in terms of m
and n)?
2. (10 points) [O3] Assume we have 7 apples, 4 oranges, and 1 banana. The apples and
oranges are identical separately. Please count the number of all permutations for each
of the following cases:
(a) put these fruits in a row;
(b) put these fruits in a circle; (orientation matters, i.e., clockwise and counter-clock
are different.)
(c) put these fruits in a row where the banana cannot be adjacent to any oranges.
3. (10 points) [O3] There are 5 balls in an opaque box, whose colors are white, red, blue,
green and yellow, respectively. They are not distinguishable unless being taken out.
Each time Amy uniformly at random takes a ball out from the box (with replacement).
(a) What is the expected number of times of taking to get the first two consecutive
white balls?
1
(b) What is the expected number of times of taking to get the first consecutive white
and red balls? (a white ball immediately followed by a red ball)
4. (10 points) [O3] There are 1000 coins, among which 999 are fair, i.e., have a head
and a tail and the probability of getting a head or a tail is equal, while 1 has heads
on both sides. Amy is playing a game: in each round, Amy picks a coin uniformly
at random and then tosses it 10 times. What is the probability of the selected coin
being unfair if Amy gets 10 heads in a round?
5. (10 points) [O3] A group of 2N people stand in a line in front of a vending machine
to buy drinks, among which each of N people holds a $5 coin, and each of the other
N people holds a $10 coin. Everyone wants only one can of drink. Drinks are all sold
at a price of $5. If the vending machine cannot give change, i.e., a person puts in
a $10 coin while there are no $5 coins in the machine, it will stop working at once.
Assume at the beginning there are no coins in the machine. People holding coins with
the same denomination are considered indistinguishable.
(a) How many queuing ways are there such that the machine will stop working when
N = 3?
(b) Let A be the set of all queuing ways that will make the machine stop working.
Each element in A consists of N 5’s and N 10’s, for example, if N = 2, an
element {5, 10, 10, 5} ∈ A denotes the first and forth person holding $5 coins and
the second and third person holding $10 coins. The machine will stop working
when the third person puts in the coin in this case. Define a function f , which
maps each element a ∈ A to a sequence of length 2N as follows: if the machine
stops working when the ith person puts in the coin in the queuing way a, then in
f(a), the first i numbers would keep unchanged while the following 5’s would be
replaced by 10’s and 10’s would be replaced by 5’s. Let f(A) = {f(a)|∀a ∈ A}.
What is the cardinality of |f(A)|?
(c) How many possible queuing ways are there such that the machine would not stop
working?
6. (10 points) [O3] Amy has a pot of coins and she decides to spend them all. Let r(i−1)
denote the number of the remaining coins after the (i− 1)th day. She comes up with
the following rule: In the ith day, she would pick a number s(i) from {1, 2, · · · , r(i−1)}
uniformly at random and spend s(i) coins. So the number of remaining coins would
be r(i) = r(i− 1)− s(i). Assume at the beginning Amy has K coins in the pot, i.e.,
r(0) = K.
(a) If K = 15, how many possible ways are there to spend all the coins in exactly 5
days?
(b) If K = 15 and Amy would spend no more than 5 coins in the first day, how many
possible ways are there to spend all the coins in exactly 5 days?
(c) If K = 6, what is the possibility that Amy would spend all the coins within the
first 5 days?
2
(d) What is the expected number of days to spend all the coins?
7. (10 points) [O3] Define S as a set of 99 natural numbers, i.e., S ⊂ N and |S| = 99.
Note that the maximum occurrence of an element in a set should be 1, that is to say,
elements are not allowed to be repeated.
(a) Let S = {1, 2, · · · , 99}. We are going to pick a subset of size 2 from S such that
the sum of the two is divisible by 3. Please count how many ways there are to
pick such subsets.
(b) Assume the elements in S are unknown to us. We want to find a set P ⊂ S such
that ∀x, y ∈ P , |x − y| ≡ 0 mod 8 (the difference of x and y is divisible by 8).
What is the maximum possible size of P for any set S (note that the size of S
must be exactly 99 while the elements can be any natural numbers)? That is to
say, what is the value of minS⊂N,|S|=99maxP⊂S |P |?
8. (10 points) [O3] There are 53 cards in a deck, including one Joker and 4 suits of cards
taking value from 1 to 13 respectively. Amy is playing a game in which she gets a
hand of 5 cards from the 53 cards in each round (with replacement). The cards are
randomly shuffled at the beginning of each round, which means Amy always has equal
probability of getting any 5 cards. Joker can be used to substitute a card of any suit
and taking any value.
(a) What is the probability that Amy can get a hand with four-of-a-kind (four of
the five cards are of the same suit) in a round?
(b) What is the probability that Amy can get a hand with a full horse (three cards
of one value and two cards of another value)?
(c) What is the probability that Amy can get a hand with two pairs (two cards of
one value and two cards of another value, the value of the fifth card differs from
both)?
9. (10 points) [O3] We are going to generate permutations from a, a, b, b, b, c, c, c, c.
Please compute the number of permutations such that: (You need to show steps.)
(a) for any consecutive 4 elements, they are not all the same;
(b) for any consecutive 3 elements, they are not all the same;
(c) for any consecutive 2 elements, they are not all the same.
10. (10 points) [O1, O3] There is a gift exchange activity among n persons. In this
activity, everyone prepares k gifts which have the same packaging. All gifts are then
put in a non-transparent box and mixed well so that they are not distinguishable.
People take gifts in turn. In the turn of a person, they takes k gifts from the box
uniformly at random one by one (without replacement).
(a) If n = 6 and k = 1, what is the probability that everyone gets a gift not prepared
by themself? (Please keep 8 significant digits.)
3
(b) If n = 6 and k = 2, what is the probability that everyone gets the two gifts
prepared by themself? (Please keep 8 significant digits.)
(c) If n = 6 and k = 2, what is the probability that everyone gets at least one gift
not prepared by themself? (Please keep 8 significant digits)?
(d) Assume k = 2. In the turn of person X, if the first gift X takes is from person
Y , what is the probability that the other gift X takes is also from Y ?