Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP 2121C Discrete Mathematics. Assignment
This Assignment 4 reviews understanding of the concepts in Topics 1, 2 and 3.
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.
1. Logic and Proofs [32 Marks]
(a) (9 marks) A propositional formula is said to be in Disjunctive Normal Form (DNF) when it is written as
a disjunction of conjunctions (an OR of ANDs). The fact that every propositional formula can be written
in Disjunctive Normal Form is useful in automated theorem proving and in the construction of digital
circuits.
Use Logical Equivalence Rules to prove that the proposition ¬ ((p→ (q ∨ r))↔ (q→ p)) is logically
equivalent to the disjunctive normal form formula (¬p ∧ q) ∨ (p ∧ ¬q ∧ ¬r).
(b) (9 marks) Consider the following propositions:
p : If Joe studies, then he will score an A in the Discrete Math course.
q : If Joe doesn’t play video games, then he will study.
r : Joe scores an A in the Discrete Math course.
s : Joe plays video games.
Determine whether the argument: (p ∧ q ∧ ¬r)→ s is valid. Explain your reasoning.
(c) (14 marks) Alice is studying for a Discrete Mathematics exam and wants to try a Backwards Induction proof
technique, proving the proposition P(k− 1) from P(k) rather than the other way round. In particular, she
considers the following predicate for n ∈ Z+:
P(n) := x1 · x2 · . . . · xn ≤
(
x1 + x2 + . . . + xn
n
)n
, if x1, x2, . . . , xn ≥ 0.
She observes a base case that since (x1 + x2)2 − 4x1x2 = (x1 − x2)2 ≥ 0, the proposition P(2) is true.
i. By setting xk as the arithmetic mean of x1, x2, . . . , xk−1 that is xk :=
x1+x2+...+xk−1
k−1 , help Alice prove
that P(k) implies P(k− 1) for any k ≥ 2.
ii. Prove that the conjunction of P(k) and P(2) implies that P(2k) is true.
iii. Explain to Alice why the above implies the truth of P(n) for all n ∈ Z+.
2. Sets, Relations and Functions [31 Marks]
(a) (10 marks) Let S be a set whose elements are finite sets. Let us define a relation R on S as follows:
R :=
{
(A, B)
∣∣A, B ∈ S and (|A| < |B| or A = B)}.
Show that R is a reflexive, antisymmetric and transitive relation, i.e., a partial order.
(b) (11 marks) For finite sets X and Y, let XY denote the set of all functions from Y to X. Suppose that A, B,K
and L are finite sets and suppose that f : A → K and g : B → L are bijections. Construct a bijective
function from the set BA to the set LK in terms of f and g.
(c) (10 marks) Solve for n ∈ Z the equation
15
(⌊n
5
⌋
−
⌊n
9
⌋)
= n.
3. Counting and Probability [37 Marks]
(a) (9 marks) Alice randomly chose 11 integers from the set S = {1, 2, 3, . . . , 100} and observed that there
were at least two chosen integers x and y for which the absolute value of the difference of their square
roots lies in the interval (0, 1), i.e.,
∣∣√x−√y∣∣ ∈ (0, 1). Prove that this must always happen irrespective of
which 11 integers Alice chooses.
(b) (9 marks) How many strings of length n can be constructed using the letters in S = {x, y, z} if the letter z
is to occur an even number of times? Prove your answer.
(c) (10 marks) At an Intervarsity Sport Bowl, your University sports team must arrange their 6 basketballs, 6
footballs, 6 volleyballs and 6 rugby balls on the 4 shelves allotted to them. How many different arrange-
ments are possible if there are to be at least 2, but no more than 7, balls on each shelf? Here all 6 balls
for each sport are identical in appearance. The 4 shelves are not identical, and in each shelf, the balls are
arranged in a linear order from left to right.
(d) (9 marks) Alice chooses two squares at random on her chessboard (an 8× 8 board with alternating black
and white squares). What is the probability that her chosen squares share a common edge?