Contents
MA375: Midterm 1 Solutions
Fall 2008, Prof. Walther
I'll put links here if anyone wants to provide solutions to the midterm.
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.) Assume you have already drawn two cards without winning. Should you pay $1 to 'chicken out' now or should you keep playing the game.
Well, since we have already drawn two non-ace cards, we only draw one more card. The probability of winning, in the same as the probability of getting an ace = $ \frac{4}{50} = \frac{2}{25} $. The probability of losing is just $ 1 - \frac{2}{25} = \frac{23}{25} $.
If we continue playing our expected payout is:
$ \begin{align} E &= $5 * \frac{2}{25} + ($-2)* \frac{23}{25} \\ &= \frac{2}{5} - \frac{46}{25} \\ &= .4 - 1.84 \\ &= -$1.44 \\ \end{align} $
Which is worse than chickening out and paying $1. So the optimal play is to chicken out.
Midterm Problem 3
Prove that for any natural number n, the quantity $ 11^n-2^n $ is divisible by 3.
Proof by induction:
Base Case: n=1, $ 11^1-2^1=9 $ and 3|9.
Assume that $ 3|(11^n-2^n) $. Show $ 3|(11^{n+1}-2^{n+1}) $.
$ 11^{n+1}-2^{n+1} = (11*11^n)-(2*2^n) $
$ =(9+2)*11^n-(2*2^n) $
$ =(9*11^n)+(2*11^n)-(2*2^n) $
$ =(9*11^n)+2(11^n-2^n) $
$ =3(3*11^n)+2(11^n-2^n) $
$ 3|3(3*11^n) $ and $ 3|2(11^n-2^n) $ by inductive hypothesis.
Midterm Problem 4
We need to determine the number of possible poker hands and the number of possible poker hands with 2-pair.
Total Number of Poker Hands:
Draw your first card: 52 possibilities
Draw your second card: 51 possibilities
Draw your third card: 50 possibilities
Draw your fourth card: 49 possibilities
Draw your fifth card: 48 possibilities
Since each card can be placed in any of the 5 spots, we divide by 5!
$ \frac{52*51*50*49*48}{5!} $
Total Number of Poker hands containing 2 pairs:
Draw your first card: 52 possibilities
Draw one of the 3 remaining cards that match the first card: 3 possibilities
Draw your third card, making sure it doesn't match the first pair: 52 - 1 - 3 = 48
Draw one of the 3 remaining cards that match the third card: 3 possibilities
Draw your fifth card making sure it doesn't match either of the pairs: 48 - 1 - 3 = 44
Since we can switch both of the pairs individually, and switch the pairs altogether, we divide by 2! * 2! * 2! = 8
$ \frac{52*3*48*3*44}{8} $
Probability of being dealt 2-pair: $ (\frac{52*3*48*3*44}{8})*(\frac{5!}{52*51*50*49*48}) $
--Aoser 23:05, 24 November 2008 (UTC)
Midterm Problem 5
Find the generating function for the recurrence $ a_n = a_{n-1} - a_{n-2} $, with $ a_0 = 0 $, $ a_1 = 1 $.
$ G_a(x)=(\displaystyle\sum_{n=0}^{\infty}a_nx^n) $
$ G_a(x)=(\displaystyle\sum_{n=2}^{\infty}a_nx^n) + a_1x^1 + a_0x^0 $
$ G_a(x)=(\displaystyle\sum_{n=2}^{\infty}a_nx^n) + x $
$ G_a(x)=(\displaystyle\sum_{n=2}^{\infty}(a_{n-1}-a_{n-2})x^n) + x $
$ G_a(x)=x(\displaystyle\sum_{n=2}^{\infty}a_{n-1}x^{n-1})- x^2(\displaystyle\sum_{n=2}^{\infty}a_{n-2}x^{n-2}) + x $
$ G_a(x)=x(\displaystyle\sum_{n=1}^{\infty}a_nx^n)- x^2(\displaystyle\sum_{n=0}^{\infty}a_nx^n) + x $
$ G_a(x)=x(\displaystyle\sum_{n=0}^{\infty}a_nx^n)-a_0x^0- x^2(\displaystyle\sum_{n=0}^{\infty}a_nx^n) + x $
$ G_a(x)=x(\displaystyle\sum_{n=0}^{\infty}a_nx^n)- x^2(\displaystyle\sum_{n=0}^{\infty}a_nx^n) + x $
$ G_a(x)=xG_a(x)-x^2G_a(x)+x $
$ G_a(x)(1-x+x^2)=x $
$ G_a(x) = \frac{x}{1-x+x^2} $
--Mkorb 12:47, 3 December 2008 (UTC)
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
