INFO 150: A Mathematical Foundation for Informatics

Solutions to Final Exam

David Mix Barrington

20 December 2017

Directions:

Answer the problems on the exam pages.
There are five problems, each with multiple parts, for 120 total points. Actual scale was A = 105, C = 75.
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. In addition, some of the true/false questions may require you to compute an explicit number, which will be less than 100.

  Q1: 15 points
  Q2: 20 points
  Q3: 25 points
  Q4: 30 points
  Q5: 30 points
Total: 120 points

Question text is in black, solutions in blue.

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

(a) two relatively prime integers and two prime integers
Two integers are relatively prime if there is no integer greater than one that divides both. An integer is prime if there is no integer greater than one that divides it, other than itself (or its additive inverse, if it is negative).
(b) the union of two sets and the intersection of two sets
The union of two sets A and B is the set of all elements that are in either A or B. The intersection is the set of all elements that are in both A and B.
(c) the expected value and the most likely value of a random variable
The expected value is a weighted average of the possible values -- it is the sum, over all possible values, of the value times its probability. The most likely value is one whose probability is greater than that of any other value.
(d) a directed graph and an undirected graph
A directed graph has edges of the form (u, v), where u and v are nodes and u = v is possible. The edge (u, v) goes from node u to node v. An undirected graph has edges of the form {u, v}, where u and v are nodes and u ≠ v. The edge {u, v} goes between the nodes u and v, without any direction.
(e) integer matrix multiplication and boolean matrix multiplication
The product of two matrices A and B has entries that are the dot product of a row vector of A and a column vector of B (and thus the length of these two types of vectors must be the same for the matrix product to be defined. In integer matrix multiplication this dot product is the integer sum, for all i from 1 through the length of the vectors, of the integer product of the i'th values of the vectors. In boolean matrix multiplication, where the matrix entries are all 0 or 1, the dot product is the OR, for all i from 1 through the length of the vectors, of the AND of the i'th values of the vectors.

Question 2 (20): The web site WeRateDogs^TM provide numerical ratings of dogs based on photographs, and publishes these at twitter.com/dog_rates. Recently they provided ratings for a set of five dogs: Ali, Cardie, Duncan, Toby, and Whistle (the set {a, c, d, t, w}). All of the ratings were integers in the set {11, 12, 13, 14, 15}. We define r(x) to be the rating of dog x, and assume that r is a function.

(a, 5) In how many ways can each dog be assigned a rating from this set, with no restrictions? (Example: r(a) = 11, r(c) = 15, r(d) = 15, r(t) = 12, r(2) = 13.)
There are five choices for each dog, for 5⁵ = 3125 in all.
(b, 5) In how many ways could the dogs be assigned ratings, if two dogs are rated 14 and the other three are all rated 12? (Example: r(a) = r(t) = 14, r(c) = r(d) = r(w) = 12.)
We must choose which set of two dogs get the 14's. This will determine the rating of all five dogs because we know that the other three get 12. There are C(5, 2) = 5×4/1×2 = 10 size-two subsets of a five-element set.
(c, 5) If each dog is independently given a random rating, with all five ratings in the set being equally likely, what is the probability that each dog gets a different rating?
Of the 3125 equally likely ratings of the five dogs, there are P(5, 5) = 5! = 120 that give each dog a different rating. So the probability is 120/3125 = 0.0384.
(d, 5) How many possiblities are there for the number of dogs that get each rating? (Example: Two dogs get 11, one gets 12, and two get 14.)

This is a "stars and bars" argument. Such a rating corresponds to a binary string with five 0's (one for each dog) and four 1's (for the barriers between the five ratings). So the rating in the example corresponds to the string 001011001. There are C(9, 4) = 9×8×7×6/1×2×3×4 = 252 such binary strings.

Question 3 (25): In this problem we will translate and reason with statements about the scenario of Question 2, using the function r defined there and the usual arithmetic, equality, and comparison symbols for integers.

(a, 5) Translate the statement "If Cardie's rating equals Duncan's, then Toby's rating is less then both Ali's and Whistle's" into a logical compound statement.
(r(c) = r(d)) → ((r(t) < r(a)) ∧ (r(t) < r(w)))
(b, 5) Translate the quantified statement "∀x:∀y: (r(x) = r(y)) → (x = y)" into English. Note that the type of x and y is "dog".
"If any two dogs have the same rating, then they are the same dog." Or, taking the contrapositive, "If any two dogs are not the same dog, then they have different ratings." Or "The function r is one-to-one."
(c, 5) Write a quantified statement that says "Some dog was rated 14, and exactly one dog was rated higher than that dog."
∃x:∃y:∀z: (r(x) = 14) ∧ ((r(z) > r(x)) ↔ (y = z)). Note that you must say both that the dog with rating higher than 14 exists, and that there are not two such dogs.
(d, 10) Explain carefully in English why, if the statement of part (b) is true, then that statement of part (c) must also be true. You may quote facts from lecture and the book if you do so clearly.
Statement (b) says that the function r is one-to-one. We know that when the domain and codomain of a function have the same size, the function is either a bijection (both one-to-one and onto) or it is neither one-to-one or onto. So r must be onto. This guarantees that there is at least one x such that r(x) = 14 and at least one y such that r(y) = 15. Statement (b) directly guarantees that there cannot be two different dogs with rating of 15, which gives us the last part of Statement (c).

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

(a) If Cardie's rating is chosen at random from the given set, with every choice equally likely, it is more likely than not to be prime.
FALSE. There are two prime numbers, 11 and 13, in the set of five possible ratings, so the probabilty is 2/5, less than the 3/5 probability of a non-prime rating.
(b) If a, b, and c are any three odd integers, then the integer ab + ac + bc must be odd.
TRUE. The product of any two odd integers is odd, so ab, ac, and bc are all odd. And the sum of any three odd integers is also odd.
(c) If I assume two statements p and q, and derive a contradiction, then I have proved (¬p) ∧ (¬q).
FALSE. I have proved ¬(p ∧ q), which by DeMorgan is (¬p) ∨ (¬q), which is not the same as (¬p) ∧ (¬q).
(d) Let p, q, and r be three propositions. If p ∧ q and r → ((¬p) ∨ (¬q)) are both true, then r must be false.
TRUE. If r were true, the second premise would force one of p and q to be false, but the first premise says that both p and q are true. Since the assumption of "r" together with the premises derives a contradiction, r must be false if both premises are true.
(e) It is possible that the function r of Questions 2 and 3 is one-to-one, but not onto.
FALSE. Any one-to-one function from a domain to a codomain of the same size must also be onto.
(f) If Cardie and Duncan are given ratings independently, with each rating equally likely, then the probability that their ratings are different is P(5, 2)/5² = 20/25 = 0.8.
TRUE. There are 5² 25 choices of the two ratings, and P(5, 2) = 20 of them have Duncan's rating different from Cardie's (since for each choice of Cardie's rating, there are four choices of Duncan's that are different from it).
(g) There exists an undirected graph with three vertices of degree three, two vertices of degree 4, and no other vertices.
FALSE. The sum of the degrees of all the vertices in an undirected graph must be even, since it is twice the number of edges. Such a graph as described would have a sum of 3×3 + 2×4 = 17, which is odd.
(h) If each of the five dogs is given a rating independently, with each rating in the set being equally likely, then the expected value of the sum of the five ratings is 65.
TRUE. The expected value of each rating is (11+12+13+14+15)/5 = 13, and the expected value of the sum is the sum of the five individual expected values.
(i) Let H be a directed graph, with no self-loops, where every node has at least one edge out of it and at least one edge into it. Let x and y be any two nodes in H. Then there must be a path in H from x to y.
FALSE. Consider a graph with six nodes {a, b, c, d, x, y} and edges (x, a), (a, b), (b, x), (y, c), (c, d), (d, y). This meets the given conditions but has no path from x to y. There is no assumption that a directed graph must be connected.
(j) Consider the two-player game where we have a pile of stones and each player on her move may take one, two, or three stones. The goal is to take the last stone. If we start with 19 stones, the first player's best move is to take three.
TRUE. The way to win this game is to leave a pile of stones of a size divisible by four. Once you do that, your opponent must leave you a number whose remainder modulo 4 is 1, 2, or 3, and you can do it again. Thus you will eventually be able to make the number 0 and win the game.

Question 5 (30): In this problem we study a Markov process derived from a simplified, one-player adaptation of the dreidel game traditionally played at Hannukah celebrations. At any time the Player has zero, one, or two chocolate coins. On each turn she spins the dreidel, which gives one of four outcomes with equal probability. She may gain or lose a coin based on this outcome:

If she has no coins, she does not gain or lose, whatever the outcome.
If she has one coin, one outcome has her lose it, one keeps her state the same, and two have her gain a coin.
If she has two coins, one outcome has her lose a coin and the other three keep her state the same.

We will define M to be the Markov process for this game, with state set {0, 1, 2}, and Z to be the transition matrix of M, with Z_ij being the probability of going from state i to state j in one step. We also define A to be the matrix such that A_ij is the number of outcomes (out of four) that take state i to state j in one step. Note that for any i and j, Z_ij = A_ij/4. We can also consider A to be the adjacency matrix of a directed multigraph G, which has node set {0, 1, 2} and has A_ij directed edges from node i to node j.

(a, 5) Write down both the matrices A and Z.


         4  0  0              1     0     0
    A =  1  1  2       Z =   1/4   1/4   1/2
         0  1  3              0    1/4   3/4

(b, 5) Compute the matrices A² and Z². (You can save a lot of calculation by using the relationship between the two.)


         16  0   0             1     0     0
  A^2 =   5  3   8      Z^2 = 5/16  3/16  1/2
          1  4  11            1/16  1/4  11/16

(c, 10) Prove, by induction on n for all n with n ≥ 1, that the last two entries of the first row of Zⁿ are both zero. (That is, (Zⁿ)₀₁ = (Zⁿ)₀₂ = 0.) What is the meaning of this fact in terms of the Markov process?
The meaning of this fact is that if the process starts in state 0, there is zero probability that after any positive number of steps, it will be in state 1 or 2.
Our statement P(n) is "(Zⁿ)₀₁ = (Zⁿ)₀₂ = 0".
Our base case is to prove P(1), which says that Z₀₁ = Z₀₂ = 0. This is true by the definition of Z, as shown in part (a).
Our inductive hypothesis is that (Z^n-1)₀₁ = (Z^n-1)₀₂ = 0.
Our inductive goal is to show that (Zⁿ)₀₁ = (Zⁿ)₀₂ = 0.
The matrix Zⁿ is equal to Z times Z^n-1. The entry (Zⁿ)₀₁ is thus the dot product of the first row of Z, (1 0 0), and the second column of Z^n-1. The first entry of that second column starts with (Z^n-1)₀₁, which by the IH is 0. The dot product is therefore 0, since the product of each pair of entries is 0. The argument for (Zⁿ)₀₂ is identical.

(d, 5) Write down the matrix Z³. You might be able to use the relationship between the matrices A and Z to save yourself some calculation.


         64  0   0             1      0      0
  A^3 =  23 11  30     Z^3 = 23/64  11/64  15/32
          8 15  41            1/8   15/64  41/64

(e, 5) If you start the Markov process in state 1, what is the probability that five steps later, you will be in state 2?
We need the dot product of the second row of Z² and the last column of Z³ (or vice versa). This is (5/16 3/16 1/2) dot producted with (0 15/32 41/64), which is (1/1024)(5×0 + 3 ×30 + 8×41) = 418/1024 = 209/512.

Last modified 14 January 2018