- 1.
- Define a set
*S*of character strings over the alphabet by the following rules:*a*is in*S*and*ab*is in*S*. If the string*x*is in*S*and*y*is in*S*, then*axb*is in*S*and*xy*is in*S*. Nothing else is in*S*. Prove that every string in*S*has at least as many*a*'s as*b*'s.**Answer**We prove this by the second principle of induction on the length of the string.*Basis:*If length=1, the string has to be*a*, so the statement is true. If length=2, the string is either*ab*or*aa*, and in both cases the statement is true*Inductive Hypothesis:*For all , strings of size*k*have at least as many*a*'s as*b*'s.*To show:*String of size*n*+1 () has at least as many a's as b's.Proof : Let

*s*be a string of size*n*+1.*Case #1:**s*can be written as*axb*, where*x*is a string in*S*of size*n*-1. By I.H.*x*has at least as many*a*'s as*b*'s. Thus,*s*has at least as many*a*'s as*b*'s.*Case #2:**s*can be written as*xy*, where*x*and*y*are both in*S*. Notice that length of*x*is , and length of*y*is By I.H.*x*and*y*each have at least as many*a*'s as*b*'s. Thus,*s*has at least as many*a*'s as*b*'s. So, in both cases,*s*has at least as many*a*'s as*b*'s.

- 2.
- Every day, starting on day 0, one vampire arrives in Seattle
from Transylvania and, starting on the day after its arrival, bites
one Seattlite every day. People bitten become vampires themselves
and live forever. New vampires also bite one person each day
starting the next day after they were bitten. Let
*V*_{n}be the number of vampires in Seattle on day*n*. So, for example,*V*_{0}= 1,*V*_{1}= 3 (one that arrived from Transylvania on day 0, one that he bit on day 1, and another one that arrived from Transylvania on day 1),*V*_{2}= 7 and so on.- (a)
- Write a recurrence relation for
*V*_{n}that is valid for any .**Answer** - (b)
- Prove by induction on
*n*that .**Answer***Basis:*for*n*=0,*V*_{0}= 1 = 3^{0}*Inductive Hypothesis:*For all , .*To show:*. Proof :

- 3.
- Permutations:
- (a)
- How many permutations of the letters {a,b,c,d,e,f,g,h} are
there?
**Answer**8! - (b)
- How many permutations of {a,b,c,d,e,f,g,h} are there that
don't contain the letters ``bad'' (appearing consecutively)?
**Answer** - (c)
- How many permutations of {a,b,c,d,e,f,g,h} are there that
don't contain either the letters ``bad'' appearing consecutively
or the letters ``fech'' appearing consecutively?
**Answer**8! - (6! + 5! - 3!) = 8! - 6! - 5! + 3! - (d)
- How many words of length 10 can be constructed using the
letters {a,b,c,d,e,f,g,h} that contain exactly 3 a's? (They
don't have to have any English meaning.)
**Answer**

- 4.
- A standard deck of 52 cards is shuffled completely (i.e., any of
the permutations is equally likely.) What is the probability that no
two spades are adjacent in the shuffled deck?
**Answer**First, place the 39 non-spade cards. There are 39! ways to do so. Then, insert each spade between two non-spade cards (or at the beginning or at the end of the deck). There are 40 places where a spade can be inserted, and so the spades can be inserted in P(40,13) ways. Thus, the total number of decks where two spades are adjacent is 39! * P(40,13) and the probability that this happens is 39! * P(40,13) / 52! - 5.
- Consider an undirected graph on
*n*vertices generated as follows. For each pair of vertices, an edge between those vertices is included in the graph with probability*p*, and not included with probability 1-*p*. What is the expected number of edges in the graph?**Answer**Let*X*be the random variable representing the total number of edges in the graph. There are C(n,2) possible pairs of vertices. Let's number them from 1 to C(n,2). Let the value of the random variable*X*_{i}= 1 if i-th pair is chosen to form an edge, and 0 otherwise. From the definition of the*X*_{i}it follows that*X*=*X*_{1}+*X*_{2}+...*X*_{C(n,2)}*E*(*X*) =*E*(*X*_{1}) + .... +*E*(*X*_{C(n,2)}) =*C*(*n*,2) **p*We could also have stated that choosing each vertex is a Bernoulli trial, where a trial is successful if the vertex is included in the graph. Therefore, the expectation is given by the number of trials (choosing a vertex, C(n,2)) times*p*. - 6.
- Suppose a biased coin with probability 3/4 of coming up heads is
tossed independently 100 times.
- (a)
- What is the conditional probability that the first 50 tosses
are heads given that the total number of heads is 50?
**Answer**P( first 50 heads total of 50 heads) =

P( first 50 heads and total of 50 heads) / P( total of 50 heads) =

) / ( C(100,50) ) = 1/ C(100,50) - (b)
- What is the expected number of heads?
**Answer**Each coin flip is a Bernoulli trial, therefore the expectation is (we could also compute it using the same idea as in exercise 5). - (c)
- Suppose that you are paid $50 if the number of heads in the
first two tosses is even and $100 if the number of heads in these
first two tosses is odd. What is your expected return?
**Answer**Let*X*= income, with*X*=50 if number of heads is even and*X*=100 if number of heads is odd. .Therefore, expected return is $550/8.

- 7.
- On the next set of questions, fill in the .
- (a)
- The number of subsets of an
*n*element set is 2^{n}. - (b)
- The number of ways of choosing an unordered subset of size
*k*out of a set of size*r*is . - (c)
- The coefficient of
*x*^{10}in the polynomial (5*x*+1)^{100}is . - (d)
- The number of different binary relations from a set
*A*of size*n*to a set*B*of size*m*is 2^{m n}. - (e)
- The number of different reflexive binary relations on a set
*A*of size*n*is 2^{n2 - n}. - (f)
- The number of different undirected graphs (no self loops and
no parallel edges) on
*n*vertices is 2^{C(n,2)}.

- 8.
- The final exam of a discrete math course consists of 50
true/false questions, each worth two points, and 25 multiple-choice
questions, each worth four points. The probability that Linda
answers a true/false question correctly is 0.9, and the probability
that she answers a multiple-choice question correctly is 0.8. What
is her expected score on the final?
**Answer**The same reasoning as in exercise 5 can be used to see that we can compute the overall expectation by summing over the expectations of the individual questions. For each true/false question, the expected number of points is . For the multiple-choice questions, the expectation is points each. Therefore, the expected score is . - 9.
- A 3-person jury has two rational members, each of whom
independently has a probability p of making the correct decision,
and a third member who just flips a coin for each decision. The
majority decision rules. A one-person jury has probability p of
making the correct decision. Which jury has a better probability of
making the correct decision? Justify your answer.
**Answer**P( correct decision) = P( majority makes correct decision). Let's denote*c*for correct and*i*for incorrect. Then,

P( majority makes correct decision) =

Thus, the 3-person jury and the 1-person jury have the same probability of making the correct decision. - 10.
- A pitcher's record is 21 wins and 4 losses. Prove that he must
have enjoyed a winning streak of 5 games.
**Answer**It's an application of the pigeon hole principle. The 4 losses divide the season in a set of winning streaks (the one before the first loss, the one between the 1st loss and the second loss, etc.). These 5 streaks are our pigeon holes. We have 21 wins (pigeons), so there must be a pigeon hole with at least ceiling(21/5) = 5 pigeons in it.