INFO 150: A Mathematical Foundation for Informatics

Solutions to Final Exam

David Mix Barrington

Exam given 16 December 2016

Solutions posted 10 January 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

Exam text is in black, solutions in blue.

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

(a) for an integer x to be a divisor of y and for x to be a multiple of y.
x is a divisor of y if y = xz for some integer z. x is a multiple of y if x = yz for some integer z.
(b) disjoint events and independent events in probability
Disjoint events have Pr(x ∧ y) = 0, i.e., they cannot both occur. Independent events have Pr(x ∧ y) = Pr(x)Pr(y) -- this is the case if neither event has any influence on the other.
(c) a symmetric relation and an antisymmetric relation
A symmetric relation has the property that for any x and y, P(x, y) → P(y, x). An antisymmetric relation has the property that for any x and y, (P(x, y) ∧ P(y, x)) → (x = y).
(d) the zero matrix and the identity matrix
The zero matrix Z has every entry zero, so that ZX = XZ = Z for any matrix X of the appropriate size. The identity matrix I has 1's on the main diagonal and 0's everywhere else, so that IX = XI = X for any matrix X of the appropriate size.
(e) a simple graph without cycles and a tree
A tree is a simple graph without cycles, but it must also be connected.

Question 2 (20): To help with the anxiety of final exams, students Xavier, Yolanda, and Zhang (the set {x, y, z}) have each been given the opportunity to pet one of the four trained therapy dogs Arly, Biscuit, Cardie, or Duncan (the set {a, b, c, d}). Here are four counting and probablity problems about the assignment of students to dogs.

(a, 5) In how many ways can each student be assigned a dog, if each student pets one dog and no two students pet the same dog? (Example: Xavier pets Biscuit, Yolanda pets Arly, and Zhang pets Cardie.)
X first has four choices of dog. Then Y has three, because the dog picked by X is excluded. Then Z has two, because the dogs picked by X and Y are excluded. By the Product Rule, there are 4 × 3 × 2 = 24 total ways to pick the dogs.
(b, 5) If each student pets exactly one dog, and no two students pet the same dog, how many possibilites are there for the set of dogs who are petted? (Example: {b, c, d}.)
The set of dogs picked must be a subset of the total set of dogs, of size 3. There are C(4, 3) = (4 × 3 × 2)/(1 × 2 × 3) = 4 possible sets, corresponding to the four choices of which dog is not chosen.
(c, 5) If each of the three students independently chooses a dog at random, with an equal probability of choosing each dog, what is the probability that no two students choose the same dog?
There are 4³ = 64 ways for each student to choose a dog, and all are equally likely. There are 24 ways for the dogs to be distinct, as we computed in part (a), so the probability is 24/64 = 3/8.
Alternatively, we could argue that X must have a new dog, then Y has a 3/4 chance of picking a dog other than X's, then Z has a 2/4 chance of picking a dog other than X's or Y's, so the probability is 1 × (3/4) × (1/2) = 3/8.
(d, 5) If each student chooses a dog and more than one student may choose the same dog, how many possibilities are there for the number of students petting each dog? (Example: Two students pet Cardie and one pets Duncan.)
This is a "stars and bars" argument. If we let a 0 represent each student, and place a 1 for the boundaries between A's and B's students, between B's and C's, and between C's and D's, we get a binary string with three 0's and three 1's, each such string representing exactly one choice of numbers of students for each dog. There are C(6, 3) = (6 × 5 × 4)/(1 × 2 × 3) = 20 such strings.

Question 3 (25): In the scenario of Question 2, let the predicate P(u, v) denote the statement "student u pets dog v". We no longer assume that each student pets only one dog.

(a, 5) Translate the statement "Xavier pets Cardie if and only if either Yolanda pets Biscuit or Zhang pets Duncan" into a logical compound statement.
P(x, c) ↔ (P(y, b) ∨ P(z, d))
(b, 5) Write a quantified statement that says "Some student pets two different dogs".
∃u:∃v:∃w: P(u, v) ∧ P(u, w) ∧ (v ≠ w)
(c, 5) Translate the quantified statement "∀v: ∃u: P(u, v)" into English. Note that the type of u is "student" and that the type of v is "dog".
For every dog, there is a student who pets that dog.
(d, 10) Explain carefully in English why, if the statement of part (c) is true, then that statement of part (b) must also be true.
There are four dogs and three students. If every dog is petted according to the statement of (c), the total number of pettings must be at least 4, one for each dog. If the statement of (b) were false, the total number of pettings could be at most 3, one for each student. So (b) must be true.

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 the relation P of Question 3 is a function, then the statement of Question 3 (c) must be true.
FALSE. Not every function is onto. For example, there is a function where every student pets Cardie.
(b) If the relation P of Question 3 is a function, the statement of Question 3 (b) may or may not be true.
FALSE. The statement of 3 (b) must be false, as there are only three students and four dogs, and in a function the students would only pet one dog each.
(c) If the students pick dogs as in Question 2 (c), then the probability that neither Xavier nor Zhang pet Cardie is less than 1/2.
FALSE. It is (3/4) × (3/4) = 9/16, greater than 1/2.
(d) If the students pick dogs as in Question 2 (c), then the probability that Yolanda and Zhang pet the same dog is 1/4.
TRUE. Yolanda's dog is one of Zhang's four equally likely choices.
(e) If x is any odd integer, then x³ - 2x² + 3x - 4 is an even integer.
TRUE. Odd - even + odd - even = even.
(f) Let P(x) be a property of positive integers. If P(1) is false, and for any n such that P(n) is true, there is a positive integer m such that P(m) is true and m < n, then P(x) cannot be true for any positive integer x.
TRUE. If P(x) were true for any x, there would have to be a smallest positive integer x for which it were true. This cannot be 1 because P(1) is false, and if it were any other number x the number m of the second assumption could not exist. (Actually we don't even need the first assumption to get a contradiction.)
(g) In the Nim game with five piles containing 3, 4, 5, 6, and 7 stones respectively, the first player has a winning strategy that begins by taking all three stones from the first pile.
TRUE. The bitwise XOR of 3, 4, 5, 6, and 7 is 3. By changing the 3 to a 0, we change the bitwise XOR to 0, which is a winning move. We can win by continuing to make the bitwise XOR 0 on each of our moves, as each of our opponent's moves will change it from 0 to something else.
(h) In a simple graph (an undirected graph with no loops or parallel edges) with n nodes, there cannot be more than 2n - 1 edges.
FALSE. There could be as many as n(n-1)/2, which is greater than 2n - 1 for most n. For example, n could be 5, and we could have as many as 5(5-1)/2 = 10 edges, but 2n - 1 is only 9.
(i) Let G be any graph that has at least three nodes and where every node has even degree. Then G contains a cycle that includes every edge exactly once.
FALSE. If G is not connected, for example if it has more than one node and no edges at all, there is no such cycle.
(j) Let G be the directed graph representing a relation R ⊆ A × A. If there is an edge from x to y in G, there is also an edge from x to y in the graph representing the transitive closure of R.
TRUE. The edge is in itself a path, and the transitive closure includes all pairs (x, y) such that there is a path from x to y.

Question 5 (30): Consider the directed multigraph G with nodes A, B, and C and directed edges from A to A, from A to B, from B to B, and from B to C, and with two directed edges from C to C. Note that this directed graph has out-degree two at every vertex. Let M be the adjacency matrix of G.

Also consider a Markov process P with the same states A, B, and C, where the probability of transitioning on each edge of G is 1/2. (Thus from C, for example, the probability of going to C is 1.) Let Z be the matrix of this Markov process.

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


       1  1  0             1/2 1/2   0
M  =   0  1  1       Z  =   0  1/2  1/2
       0  0  2              0   0    1

(b, 5) Compute the matrices M² and M³.


        1  2  1            1  3  4
 M^2 =  0  1  3      M^3 = 0  1  7
        0  0  4            0  0  8

(c, 10) Prove, by induction on n for all n with n ≥ 1, that the matrix Mⁿ is given by:
```
		  1    n     2^n - n - 1
		  0    1       2^n - 1
		  0    0         2^n
	      
```
For the base case, we plug n = 1 into the given matrix and confirm that the result is exactly n.
The IH is that M^n-1 is the matrix:
```
		  1   n-1   2^{n-1} - (n-1) - 1
		  0    1        2^{n-1} - 1
		  0    0           2^{n-1}
	      
```
The inductive goal is that Mⁿ is the given matrix. To confirm this, we multiply M by the matrix above for M^n-1. The top row of the result is the sum of the top and middle rows of M^n-1, which is exactly (1, n, 2ⁿ - n - 1) as it should be. The middle row of the result is the sum of the middle and bottom rows of M^n-1, which is (0, 1, 2ⁿ - 1) as it should be. And the bottom row of the result is twice the bottom row of M^n-1, which is (0, 0, 2ⁿ) as it should be.
(d, 5) Write down the matrix Z³. You might be able to use the relationship between the matrices M and Z to save yourself some calculation.
Since Z = (1/2)M (in that every entry of Z is half the corresponding entry of M), z³ is just (1/2)³M³ = (1/8)M³ which is:
```
                          1/8 3/8  1/2
                     Z^3 = 0  1/8  7/8
                           0   0    1
	
```
(e, 5) If you start the Markov process in state A, what is the probability that six steps later, you will be in state C?
We need the (A, C) (or top right) entry of the matrix Z⁶. This is the dot product of the top row of Z³ and the right column of Z³, which is (1/8 × 1/2) + (3/8 × 7/8) + (1/2 × 1) = 4/64 + 21/64 + 32/64 = 57/64.
We could also use the result of (c) to find that the top right entry of M⁶ is 2⁶ - 6 - 1 = 57, so that the top right entry of Z⁶ is (1/2)⁶ times that, or 57/64.

Last modified 10 January 2017