INFO 150: A Mathematical Foundation for Informatics

Solutions to Second Midterm Exam

David Mix Barrington

28 November 2016

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Actual scale was A = 85, B = 70, C = 55, D = 40.
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.

Question text is in black, solutions in blue.

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

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

(a) for a set C to be the intersection of sets A and B
C must contain exactly those elements that are common to A and B.
(b) for a relation R ⊆ A × B to be a function
The relation is a function if for every element a of A, there is exactly one element b of B such that (a, b) is in R.
(c) for a relation R ⊆ A × A to be reflexive
R is reflexive if for every element a of A, (a, a) is in R.
(d) the Sum Rule for computing probabilities
If A and B are disjoint events (they cannot both happen), then Pr(A ∪ B) = Pr(A) + Pr(B). In general, the Sum Rule With Overlap says that Pr(A ∪ B) = Pr(A) + Pr(B) - Pr(A ∩ B). (Either rule was sufficient for full credit.)
(e) the sample space for a probability problem
The sample space is the set of all possible atomic events that might occur.

Question 2 (25): Let D = {a, b, c, d, e} be a set consisting of the five dogs Arly, Biscuit, Cardie, Duncan, and Ebony. Let K = {k₁, k₂, k₃, k₄} be a set of four kennels. The following four counting problems involve putting these dogs into the kennels.

(a, 5) In how many ways can each dog be assigned a kennel? (Example: Arly and Duncan in k₁, Ebony in k₂, no one in k₃, and Biscuit and Cardie in k₄.)
There are four choices for each dog, so by the product rule the total is 4×4×4×4×4 = 4⁵ = 1024. Many people said "5⁴", indicating that they tried to memorize a formula instead of understanding the reason for it.
(b, 5) Suppose Arly, Biscuit, and Ebony are all put in k₄. In how many ways could Cardie and Duncan be put into some of the other three kennels, without their both going in the same kennel? (Example: Cardie in k₂ and Duncan in k₃.)
Cardie may go into any of the three kennels, after which there are two remaining kennels into which Duncan might go, so by the Product Rule there are 3×2 = 6 total choices. This is also P(3, 2), the number of ways to choose two of the three kennels in order, without replacement.
(c, 5) In how many ways could we choose a set of exactly three of the five dogs to go into k₄?
There are C(5, 3) = (5×4×3)/(1×2×3) = 10 possible size-3 subsets of the size-5 set D.
(d, 10) If more than one dog may go in a kennel, how many ways are there to decide how many dogs are in each kennel? (Example: two in k₁, none in k₂, one in k₃, two in k₄.)
By the "stars and bars" argument, we have a binary string with a 0 for each dog and a 1 for each division between kennels (between k₁ and k₂, between k₂ and k₃, and between k₃ and k₄. So we must count the binary strings with 5 0's and 3 1's, of which there are C(8, 3) = (8×7×6)/(1×2×3) = 56.

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 2a counts the total number of functions from K to D.
FALSE. It counts the functions from D to K.
(b) Question 2b counts the total number of one-to-one functions from {c, d} to {k₁, k₂, k₃}.
TRUE.
(c) Question 2c's answer is the number of ways we can choose two dogs that will not go into k₄.
TRUE. Choosing three dogs to go into k₄ means deciding which two dogs will not go there.
(d) Question 2d's answer is the number of binary strings with exactly five 0's and exactly three 1's.
TRUE. This is the "stars and bars" argument given above.
(e) Every function counted in Question 2a is onto.
FALSE. All five dogs might go into k₁, for example, leaving the others empty.
(f) Some of the functions counted in Question 2a are one-to-one.
FALSE. There are no one-to-one functions from the five dogs to the four kennels, by the Pigeonhole Principle.
(g) The direct product D × K has more elements than does the power set of K.
TRUE. D × K has 5 × 4 = 20 elements, while P(K) has 2⁴ = 16.
(h) If we pick one of the assignments in Question 2a, then the relation R(x, y) meaning "dog x and dog y are put into the same kennel" is reflexive and symmetric but not antisymmetric.
TRUE. This is an equivalence relation, which is reflexive, symmetric, and transitive. It is not antisymmetric because it is possible (indeed certain) that two different dogs will go in the same kennel, making R(x, y) and R(y, x) both true with x ≠ y.
(i) There are exactly 4³ functions counted in Question 2a that have Arly and Biscuit in the same kennel, and also have Cardie and Duncan in the same kennel.
TRUE. We have four choices as to where to put Arly and Biscuit, four choices where to put Cardie and Duncan, and four choices where to put Ebony. By the Product Rule there are 4×4×4 = 4³ total choices.
(j) If we put each of the dogs in some kennel, and no kennel is empty, then exactly one kennel must have exactly two dogs in it.
TRUE. After one dog is put in each kennel, the fifth dog must go somewhere, making that kennel have two dogs while the other three kennels have one each.

Question 4 (30): For this question we begin with a 52-card deck, containing 13 spades, 13 hearts, 13 diamonds, and 13 clubs. We are dealt three cards without replacement.

(a, 5) What is the expected number of spades in our hand?
The expected number of spades in the first card is 1/4, because there is a 1/4 probability that this card is a spade. (The formula gives us Pr(one spade)(1) + Pr(no spades)(0) = 1/4.) Similarly the expected number in the second card is 1/4, and in the third card is 1/4. The total number of spades is the sum of these three values, so the expected value of the total number of spades is 1/4 + 1/4 + 1/4 = 3/4.
(b, 5) What is the probability that our hand contains no spades?
Method 1: There are C(52, 3) possible three-card hands, and C(39, 3) three-card hands made from the 39 non-spades in the deck. So we have a probability of C(39, 3)/C(52, 3) = (39×38×37)/(52×51×50) = 0.4135. (You were not expected to evaluate this arithmetic expression.)
Method 2: The first card is a non-spade with probability 39/52. If it is a non-spade, the second card is also a non-spade with probability 38/51, since there are now 38 non-spades in 52-card deck. If the first two are not spades, we complete the hand of three non-spades with probability 37/50, so the total probability by the Product Rule is (39/52)\times;(38/51)×(37/50) = 0.4135.
(c, 5) What is the probability that our three cards are of three different suits?
Method 1: There are C(4, 3) = 4 ways to choose which three suits, and then 13 ways to choose a card of each suit, so we have 4×13³ = 8788 three-card hands with three different suits. We divide this number by C(52, 3) = 22100 to get 0.3976.
Method 2: The first card is a new suit with probabilty 1. The second card is not the same suit as the first with probability 39/51. If the first two cards are of different suits, the third card is a new suit with probability 26/50. So the probability is 1×(39/51)×(26/50) = 0.3976.
(d, 5) What is the probability that our three cards are all of the same suit?
Method 1: There are C(4, 1) = 4 choices of suit, then C(13, 3) = 286 choices of three cards from that suit, for a total probability of 4*C(13, 3)/C(52, 3) = 1144/22100 = 0.0518.
Method 2: The first card is from some suit. The second card is of the same suit with probability 12/51. If the first two cards are of the same suit, the third is of that suit with probability 11/50. So we have (12/51)×(11/50) = 132/2550 = 0.0518.
(e, 10) Are we more likely to have an even number of spades or an odd number of spades in our hand? Or is there a 1/2 probability of each of these outcomes? Explain your answer -- a correct answer with no explanation will get only three points. (Remember that 0 is an even number.)
This problem was too hard for this exam, as I realized later. (In effect, by moving the A line from 90 down to 85 I made this problem half extra credit.)
Of the C(52, 3) = 22100 three-card hands, C(39, 3) = 9139 have no spades, and C(13, 3) = 286 have four spades. How many have exactly one spade? There are 13 way to pick the spade and C(39, 2) ways to pick the two non-spades, for 13×((39×38)/(1×2)) = 9633. With exactly two spades, there are C(13, 2) = 78 ways to pick the two spades and 39 ways to pick the one non-spade, for 78×39 = 3042. Since 9139 + 3042 = 12181 is greater than 9633 + 286 = 9919, there is a larger chance of getting an even number. But this was more arithmetic than I should reasonably have expected you to do.
An approximation that gives the right answer in this case is to replace the cards after each one is drawn, so that we have three Bernoulli trials with probability 1/4. Then the probability of no successes (no spades) is (3/4)³ = 27/64, of one spade is C(3, 1)(1/4)(3/4)² = 27/64, of two spades is C(3, 2)(1/4)²(3/4) = 9/64, and of three spades is (1/4)³ = 1/64. Then because 27/64 + 9/64 is greater than 27/64 + 1/64, there is a larger chance of an even number of spades. But to use this method you would need to be confident that the lack of replacement does not change the probabilities very much.

Last modified 28 November 2016