Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP2121A: Discrete Mathematics
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?