Problem Set 4
MA221 Discrete Mathematics
Date: Oct 17, 2024
1. (a) Write the numbers 1, 2, · · · , 2n on a blackboard, where n is an odd integer.
Pick any two numbers, j and k, write |j − k| on the board and erase j and k.
Continue this process until only one integer is written on the board. Prove that
this integer must be odd.
(b) Prove that between every rational and every irrational number there is an
irrational number.
(c) Prove or disprove that if a and b are rational numbers, then ab is also rational.
(d) Show that if a, b and c are real numbers and a 6= 0, then there is a unique
solution of the equation ax + b = c.
(e) Let P (x) be the statement “Student x knows calculus” and let Q(y) be the
statement “Class y contains a student who knows calculus.” Express each of
these as quantifications of P (x) and Q(y).
(i) Some students know calculus.
(ii) Not every student knows calculus.
(iii) Every class has a student in it who knows calculus.
(iv) Every student in every class knows calculus.
(f) Use resolution to show the hypothesis “Allen is a bad boy or Hillary is a good
girl” and “Allen is a good boy or David is happy” imply the conclusion “Hillary
is a good girl or David is happy”.
(g) What rules of inference are used in this argument? “No man is an island.
Manhattan is an island. Therefore, Manhattan is not a man”.
(h) Use mathematical induction to show that given a set of n + 1 positive integers,
none exceeding 2n, there is at least one integer in this set that divides another
integer in this set.
2
(i) Show that n lines separate the plane in to n +n+2 2
regions if no two of these
lines are parallel and no three pass through a common point.
(j) Use well ordering property to show that the following form of mathematical
induction is a valid method to prove that P (n) is true for all positive integers
n.
Basis Step: P (1) and P (2) are true.
Inductive Step: For each positive integer k, if P (k) and P (k + 1) are both true,
then P (k + 2) is true.
(k) Show that [(p1 → p2 )∧(p2 → p3 )∧· · ·∧(pn−1 → pn )] → [(p1 ∧p2 ∧· · · pn−1 ) → pn ]
is a tautology whenever p1 , p2 , · · · , pn are propositions, where n ≥ 2.
(l) Prove that a set with n elements has n(n−1)(n−2)
6
subsets containing exactly 3
elements whenever n is an integer greater than or equal to 3.
(m) Prove that every simple polygon with at least four sides has an interior diagonal.
√
(n) Use strong induction to prove that 2 is irrational.
(o) Show that the principle of mathematical induction and strong induction are
equivalent; that is, each can be shown to be valid from the other.
(p) Prove that if T is a full binary tree, then n(T ) ≤ 2h(T )+1 −1, where n(T ) denotes
the number of vertices in T and h(T ) denotes the height of T .
(q) Let F be the function such that F (n) is the sum of first n positive integers.
Give a recursive definition of F (n).
(r) Recursively define the set of binary strings that have more zeroes than ones.
Best wishes
Page 2