INFO 150: A Mathematical Foundation for Informatics

Solutions to Practice Second Midterm Exam

David Mix Barrington

14 November 2016

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Scale will be determined after the exam but a good guess is A = 90, C = 60.
If you need extra space use the back of a page.
No books, notes, calculators, or collaboration.
Numerical answers may be given as expressions using addition, subtraction, multiplication, division, exponentiation, and the factorial function. But expressions such as P(n, k) or C(n, k) must be rewritten to use only these operations.

  Q1: 15 points
  Q2: 25 points
  Q3: 30 points
  Q4: 30 points
Total: 100 points

Question text is in black, solutions in blue.

Question 1 (15): Briefly identify the following terms or concepts (3 points each):

(a) for a set A to be a subset of a set B
A is a subset of B if every element of A is also an element of B.
(b) for a function from A to B to be onto
The function f from A to B is onto if for every element b of B, there is at least one element a of A such that f(a) = b.
(c) for a relation R ⊆ A × A to be antisymmetric
The binary relation R on A is antisymmetric if for every two elements x and y of A, if (x, y) and (y, x) are both in R, then x = y. That is, if x ≠ y, at least one of (x, y) and (y, x) is not in R.
(d) the Product Rule for counting (finding the size of sets)
If A and B are any two finite sets, the Product Rule says that the number of elements in the direct product A × B is the number in A times the number in B.
(e) for two events to be independent
Two events A and B are independent if their probability satisfies the rule Pr(A ∩ B) = Pr(A)Pr(B). That is, elements in A are no more or less likely to be in B than elements not in A.

Question 2 (25): Let T = {s, m, l} be a set of three dog treats (small, medium, and large) and let D = {a, b, c, d, e} be a set of five dogs (Arly, Biscuit, Cardie, Duncan, and Ebony}. Answer the following counting problems involving giving these treats to these dogs.

(a, 5) In how many ways could the treats be given to the dogs if no dog can get more than one treat (Example: small treat to Duncan, medium to Ebony, and large to Cardie)
There are five choices of whom to give the small treat, then four other dogs who could get the medium, and finally three dogs who could get the large. The total number is 5 × 4 × 3 = 60.
(b, 5) In how many ways could the treats be given to the dogs if we also allow a dog to get more than one treat (Example: small and large to Arly and medium to Biscuit)
There are five choices of whom to give the small treat, five choices for the medium, and five for the large. The total number is 5 × 5 × 5 = 125.
(c, 5) If no dog gets more than one treat, how many ways are there to choose which dogs get a treat? (Example: Arly, Cardie and Duncan get treats)
The number of size-3 subsets of D is C(5, 3) which is 5 × 4 × 3 / 1 × 2 × 3 = 10.
(d, 10) If dogs may get more than one treat, how many ways are there to choose which dogs get how many treats? (Example: Biscuit gets two and Ebony gets one.)
We make a "stars and bars" argument by assigning each such distribution a binary string with three 0's for the treats, a 1 between Arly's treats and Biscuit's, a 1 between Biscuit's and Cardie's, a 1 between Cardie's and Duncan's, and a 1 between Duncan's and Ebony's. The number of strings with three 0's and four 1's is C(7, 3) = 7 × 6 × 5 / 1 × 2 × 3 = 35.

Question 3 (30): These are true/false questions about the scenario of Question 2, with no explanation needed or wanted and no penalty for guessing (3 points each):

(a) Question 2b counts the total number of functions from T to D.
TRUE. Every treat is mapped to the dog who gets it.
(b) Question 2a counts the total number of one-to-one functions from T to D.
TRUE. One-to-one means that no dog may get more than one treat.
(c) Let R ⊆ D × D be the set of pairs (x, y) such that dogs x and y get the same number of treats. Then R is an equivalence relation.
TRUE. This relation is reflexive (x and x get the same number), symmetric (if x and y get the same number, so do y and x) and transitive (if x and y get the same number and y and z do as well, then so do x and z).
(d) The power set of D has exactly 25 elements.
FALSE. It has 2⁵ = 32.
(e) The direct product T × D has exactly 3⁵ elements.
FALSE. It has 3 × 5 = 15.
(f) There exists an onto function from T to D.
FALSE. An onto function would give at least one treat to each dog, which is impossible as there are fewer treats than dogs.
(g) There are exactly 2¹⁵ relations from T to D (relations R ⊆ T × D).
TRUE. The set of such relations forms the power set of T × D, and this direct product has 3 × 5 = 15 elements.
(h) Question 2d counts the number of ways to add five non-negative integers to get 3, such as "0+1+0+2+0 = 5".
TRUE. That sum would correspond to Biscuit getting one treat and Duncan two.
(i) Question 2c counts the power set of D.
FALSE. It counts only those subsets that have three elements. The power set includes all subsets of all sizes.
(j) No function from T to D has an inverse.
TRUE. An invertible function must be both one-to-one and onto, and no such function can be onto.

Question 4 (30): In this problem we "throw 3D6", which means that we throw three independent fair six-sided dice, numbered {1, 2, 3, 4, 5, 6}, and add the results.

(a, 5) What is the expected value of the sum of the three dice?
The expected value of each die is (1+2+3+4+5+6)/6 = 7/2. The expected value of the sum is the sum of the expected values, which is 7/2 + 7/2 + 7/2 = 21/2.
(b, 5) What is the probability that the sum is 18?
This happens only if each die comes up 6, which would be three independent events each of probability 1/6. The probability of this is (1/6)³ = 1/216.
(c, 5) What is the probability that the sum is 7?
We need to find the number of sequences of three elements of {1, 2, 3, 4, 5, 6} that add to 7. These are 115, 124, 133, 142, 151, 214, 223, 232, 241, 313, 322, 331, 412, 421, and 511: 15 sequences. Each has probability 1/216, so the probability of 7 is 15/216 or 5/72.
(d, 10) What is the probability that the sum is odd? Justify your answer (there are several different valid ways to do so). A correct answer with no justification will get only 3 points.
The probability is 1/2. Each die has an odd value with probability 1/2, and we get an odd value overall by the three dice going OOO, OEE, EOE, or EEO, four events each of which have probability (1/2)³ = 1/8 and which are pairwise disjoint.

Last modified 14 November 2016