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, the following game has recently started to become popular. You draw 3 cards, and if 1 of them is an Ace you win $5. Otherwise you lose $2.
P(losing)
a.) Compute the probability of losing the game
Ways to win the game
A A A. There are 24 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 24+1,728+27,072 and you get 28,824. 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,776 / 132,600 you get about 78%
Expected Payoff
b.) What is the expected payoff for you in this game? What you do here is take the probability of you winning the game and multiply the payoff for winning then subtract the probablity of you losing and multiply it by the amount you will have to pay if you lose.
P(win)($5) - P(lose)($2)
[(28824 / 132600)($5) - (103776 / 132600)($2) ]
So the expected payoff is $1.09 - $1.56 so you stand to lose $.47
Chickening out
c.)
Midterm Problem 3
Midterm Problem 4
Midterm Problem 5
Midterm Problem 6
Midterm Problem 7
There are 3 choices for each of the n fish: They are left in the pond. They are caught but not eaten. They are caught and eaten. So there are 3^n ways.
I think this problem would be much harder if he didn't provide us with the final solution... ~ysuo
