FINAL EXAM

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.

CS 2214: Discrete structures for computing

# FINAL EXAM CS 2214B: DISCRETE STRUCTURES FOR COMPUTING

$30.00