Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP 2121C Discrete Mathematics. Assignment 3
Ravi
(Dated: March 18, 2024)
This Assignment 3 tests understanding of the concepts of Counting and Probability.
Students are expected to work on the assignment for a period of up to two weeks and submit their
solutions through Moodle. Typically, the solution sheet will be formatted in LaTeX but any clear,
legible solution sheet will be accepted. Answers will be judged on correctness, as well as evidence
of detailed understanding, so please show working and explain the steps leading to the final solution.
Assignment 3 Due Date: March 30th 2024, 23:59.
1. Basics of Counting [17 Marks]
(a) (5 marks) Let A := {1, 2, 3, 4, 5} and B := {a, b, c, d, e, f } and consider functions with domain A and
codomain B. How many functions f : A→ B are not injective?
(b) (5 marks) How many numbers between 300 and 3000 can be formed using the digits in {0, 1, 2, 3, 4, 5} if
repetition of digits is not allowed? How many of these numbers are odd?
(c) (7 marks) Consider all 5 letter words, with or without meaning formed using the letters a through h.
i. How many of these words are there in total?
ii. How many of these words either start with the string aha or end with the string bah or both?
iii. How many of the words containing no repeated letters also do not contain the string bad?
2. Permutations and Combinations [25 Marks]
(a) (7 marks) In how many ways can the letters of the word PERMUTATIONS be arranged if
i. the arrangement starts with R and ends with S?
ii. the vowels are all together in the arrangement?
iii. there are exactly 5 letters between P and S in the arrangement?
(b) (5 marks) A circular r-permutation of n people is a seating of r of these n people around a circular table,
where two seatings are considered to be the same if they can be obtained from each other by rotating the
table. Find the number of circular 5-permutations of a group of 8 people.
(c) (6 marks) A poker hand consists of 5 cards drawn randomly from the deck. How many poker hands
contain more queens than jacks?
(d) (7 marks) Alice has observed that for any n ∈ Z+, the following identity holds:
n
∑
k=0
(
n
k
)2
=
(
2n
n
)
.
i. Show Alice how to prove the identity using the Binomial Theorem and the fact that (1 + x)2n =
(1 + x)n(1 + x)n.
ii. Suggest an alternative combinatorial proof of the identity.
3. Counting Techniques [25 Marks]
(a) (6 marks) How many integers are there between 1 and 10000 such that the sum of the digits is 14, the units
digit lies between 2 and 5, and the tens digit lies between 3 and 6?
(b) (6 marks) Show that in a group of ten people where any two people are either friends or enemies, there
are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four
mutual friends.
(c) (7 marks) Alice is sending gifts to five of her friends and has addressed the corresponding gift parcels. In
how many ways can the gifts be placed in the parcels such that at least three gifts are in the wrong parcels?
(d) (6 marks) A parent tells you that her child watched TV for at least one hour each day during a summer
recess of seven weeks but never more than 11 hours in any one week. Prove that there is some period
of consecutive days during which the child watched exactly 20 hours of TV. It is assumed that the child
watched TV for a whole number of hours each day.
4. Basics of Probability Theory [13 Marks]
(a) (7 marks) An investment company estimates that the probability that stocks a and b go up is 68% and 77%,
respectively. Let A denote the event that stock a goes up, and let B denote the event that stock b goes up.
Assume for simplicity that a stock can only go up or go down.
i. Assuming that the events A and B are independent, compute the probability that both stocks go up.
ii. Show that the probability that both stocks go up cannot be smaller than 45%, no matter whether
events A and B are independent or not.
iii. Suppose that it is impossible for both stocks to go down. Compute the probability that both stocks go
up.
(b) (6 marks) A particular roulette wheel works as follows. When the wheel is spun once, there are 38 possible
outcomes: 18 red, 18 black, and 2 green. In each spin, all outcomes are equally likely, and successive spins
are independent of each other. If you are told that in two spins at least one resulted in a green outcome,
what is the probability that both outcomes were green?
5. Probability Distributions, Expected Value and Variance [20 Marks]
(a) (5 marks) Compute the probability that a uniformly generated 12-bit string begins with a 1 or ends with a
00.
(b) (7 marks) Alice goes to a casino where the following games are offered based on fair six-sided dice. Game
1 costs $3 to play per round and has the following rule: in each round, Alice gets to roll a fair dice once
and receives the number of dollars that is equal to the value on the top face. Game 2 costs $4 to play
per round and has the following rule: in each round, Alice gets to roll a fair dice twice and receives the
number of dollars that is the maximum of the two values that show up on the top face. Explain to Alice
whether she would be better off choosing Game 1 or Game 2.
(c) (8 marks) Suppose that X1 and X2 are independent Bernoulli trials each with probability 1/2, and let
X3 = (X1 + X2) mod 2.
i. Show that X1, X2 and X3 are pairwise independent, but X3 and X1 + X2 are not independent.
ii. Show that V (X1 + X2 + X3) = V(X1) +V(X2) +V(X3) where V(X) denotes the variance of random
variable X.