Question 1. (a) Which of these relations on the set of all people are equivalence relations? Determine the properties of an equivalence relation that the others lack.

i.  {(a, b) : a and b are the same age}
ii. {(a, b) : a and b have the same parents}
iii. {(a, b) : a and b share a common parent}
iv. {(a, b) : a and b have met}
v.  {(a, b) : a and b speak a common language}

(b) Let R be the relation on the set of ordered pairs of positive integers, Z⁺ × Z⁺, such that

(a, b)R(c, d) if and only if ad = bc.

(For instance, (2, 4)R(6, 12) since 2.12 = 4.6.) Show that R is an equivalence relation.

Remarks. This is basically a general view of how we define two fractions being ‘equal', i.e. a/b = c/d if and only if ad = bc which means that equality of rational numbers is an equivalence relation on Q.

Question 2. (a) How many numbers must be selected from the set A = {1, 3, 5, 7, 9, 11, 13, 15} to guarantee that at least one pair of these numbers add up to 16? Explain and justify your answer.

(b) There are 51 prisoners in Paradise Correction Centre. Each inmate has a prisoner ID number from 1000 to 1099, inclusive. Give a short and clever convincing argument that at least two prisoners have ID numbers that are consecutive integers.

Quesiton 3. This question is on mathematical induction. To be considered for a full mark, you must clearly indicate your base step, inductive hypothesis, and where you do apply the inductive hypothesis.

(a) Show that. Σ_j=0ⁿ(j + 1) = ((n + 1)(n + 2))/2 whenever n is a nonnegative integer.

(b) Show that 3ⁿ < n! if n is an integer greater than 6.

Question 4. (a) How many strings of four decimal digits that

i. do not contain the same digit three times?

ii. end with an even digit?

iii. have exactly three digits that are 9s?

(b) In how many ways can a photographer at a wedding arrange 6 people in a row from a group of 10 people, where the bride and the groom are among these 10 people, if

i. the bride must be next to the groom?

ii. the bride is not next to the groom?

iii. the bride is positioned somewhere to the left of the groom?