CS 2214B: DISCRETE STRUCTURES FOR COMPUTING
Instructions: Please submit a single pdf file to gradescope. Each question is worth 20
points.
1. Let n be an odd number and X be a set with n elements. Find the no. of subsets of
X which has even no. of elements. The answer should be a number depending only
on n. (For example, when n = 5, you need to find the no.of subsets of X which has
either 0 elements or 2 elements or 4 elements)
2. Let p1, . . . , pn+1 be n points inside a circle C such that none of them are the center
of C. Let l1, . . . , ln+1 be the lines (radii) connecting the center and p1, . . . , pn+1
respectively. Prove that there are two distinct lines li and lj such that the (smaller)
angle between them is at most 2π
n
.
3. Let S be a finite set of propositions. We define a relation R on S as follows: we say
a proposition p ∈ S is related to a proposition q ∈ S by R iff p ∧ q = T. Is R an
equivalence relation? Explain why or why not.
4. Prove that
n
k
?
is divisible by n for all 1 ≤ k ≤ n − 1, when n is a prime number.
Give an example of a positive integer m such that m does not divide m
k
?
for some
1 ≤ k ≤ m − 1.
5. A set of propositions {pn : n ∈ N} are defined inductively as follows:
i. p0 = T and p1 = T.
ii. pn+1 = (pn −→ pn−1).
Prove that pn = T for all n ≥ 2 using induction.
