1.

Define a set S of character strings over the alphabet $\{a,b\}$ 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 $1 \leq k \leq n$, strings of size k have at least as many a's as b's. To show: String of size n+1 ($n \geq 2$) 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 $\leq n$, and length of y is $\leq n$ 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₀ = 1, V₁ = 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₂ = 7 and so on.

(a)

Write a recurrence relation for V_n that is valid for any $n \ge 2$. Answer $V_n = 2 \cdot V_{n-1} + 1$

(b)

Prove by induction on n that $V_n \le 3^{n}$. Answer Basis: for n=0, V₀ = 1 = 3⁰

Inductive Hypothesis: For all $1 \leq k \leq n$, $V_n \leq 3^n$. To show: $V_{n+1} \leq 3^{n+1}$. Proof :

$$\begin{eqnarray*}V_{n+1} &=& 2 \cdot V_n + 1\\ & \leq & 2 \cdot 3^n + 1\\ & ... ...dot 3^n + 1 + (3^n - 1)\\ & = & 3 \cdot 3^n\\ & = & 3^{n+1} \end{eqnarray*}$$

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 $8! - (6 \cdot 5!) = 8! - 6!$

(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 $C(10,3) \cdot 7^7$

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. $E(X_i) = 1 \cdot p + 0 \cdot (1-p) = p$ From the definition of the X_i it follows that X = X₁+X₂+...X_C(n,2)

E(X) = E(X₁) + .... + 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 $\mid$ total of 50 heads) =
P( first 50 heads and total of 50 heads) / P( total of 50 heads) =
$((3/4)^{50} \cdot (1/4)^{50}$) / ( C(100,50) $\cdot (3/4)^{50} \cdot (1/4)^{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 $100 \cdot p = 75$ (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. $E(X) = 50 \cdot P( X = 50) + 100 \cdot P(X=100) =\\ 50 \cdot P( \mbox{even nu... ... 1/4\cdot3/4 + 3/4\cdot1/4) =\\ 50 \cdot (5/8) + 100 \cdot (3/8) =\\ 550/8$.

Therefore, expected return is $550/8.

7.

On the next set of questions, fill in the $\ldots$.

(a)

The number of subsets of an n element set is 2ⁿ.

(b)

The number of ways of choosing an unordered subset of size k out of a set of size r is $C(r,k) = \frac{r!}{k! \cdot (r-k)!}$.

(c)

The coefficient of x¹⁰ in the polynomial (5x+1)¹⁰⁰ is $5^{10} \cdot C(100,10)$.

(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 $0.9 \cdot 2 = 1.8$. For the multiple-choice questions, the expectation is $0.8 \cdot 4 = 3.2$ points each. Therefore, the expected score is $50 \cdot 1.8 + 25 \cdot 3.2 = 170$.

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) =
$P(ccc) + P(cci) + P(cic) + P(icc) =\\ p^2 \cdot1/2 + p^2 \cdot1/2 + p \cdot (1-p) \cdot 1/2 + (1-p) \cdot p \cdot 1/2 = \\ p^2 + p (1-p) =\\ p$ 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.