I'll put links here if anyone wants to provide solutions to the midterm.
Contents
Midterm Problem 1
Call An the number of binary strings of size n without double zeroes. We can put each of the strings in An in one of three separate groups:
- Strings that begin with 10 or 11 (ie begin with 1): 1|(n-1 digits)
- Strings that begin with 01: 01|(n-2 digits)
- Strings that begin with 00: 00|(n-2 digits)
Clearly the third group has no members. Further if the entire string is assumed to have no double zeroes, then the (n-1 digits) and (n-2 digits) have no double zeroes either. Thus there are An-1 strings in the first group and An-2 strings in the second group.
Thus, An=An-1+An-2, and since A0=1, A1=2, this defines the recurrence relation.
Midterm Problem 2
In Las Vegas
a.) compute the probability of losing the game
Ways to win the game
A A A. There are 48 different ways to get all three Ace's
A A_, A _ A, or _ A A. There are 1,728 ways to get two Ace's and any other card. Three cards (say A A _) you have a 4 ways to get the first Ace and 3 ways to get the next Ace then 48 ways to get the last card. Multiply them (4*3*48) and you get 576, then multiply that by 3, since there are three ways to get two Ace's. and you get 1728.
A_ _, A _ A, or _ _ A. There are 27,072 ways of getting one Ace and two other non Ace cards. Same logic as above.
Then you add 48+1,728+27,072 and you get 28,848.Now if you divide that by one minus the total number of outcomes of choosing any 3 cards (52*51*50) which equals 132,600. So 103,751 / 132,600 you get about 78%
b.)
