Discrete Structures Anna Karlin
CSE 321, Spring 2000

Practice Questions
from previous exams

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 by induction that every string in S has at least as many a's as b's.

2.

True or false:

• $Pr(A\bigcup B) \le Pr(A) + Pr(B)$.
  
  
• For any event A in a probability space $0 \le Pr(A)\le 1$.
  
  
• For any events A and B in a probability space $Pr(A\mid B) = Pr(A)$.
  
  
• An undirected graph has an even number of vertices of odd degree.
  
  

3.

On the next set of questions, fill in the blanks.

• The number of subsets of an n element set is
  
  
• The number of ways of choosing an unordered subset of size k out of a set of size r is
  
  
  
  
• The coefficient of x¹⁰ in the polynomial (5x+1)¹⁰⁰ is
  
  
• The number of different binary relations from a set A of size n to a set B of size m is
  
  
• The number of different reflexive binary relations on a set A of size n is
  
  
• The number of different undirected graphs (no self loops and no parallel edges) on n vertices is
  
  

4.

Define a function g on the non-negative integers by g(0)=2, g(1)=3 and g(n+1)=3g(n)-2g(n-1) for all $n\ge 1$. Use strong induction to prove that for all $n\ge 0$, g(n)= 2ⁿ + 1.

5.

• 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. Write a recurrence relation for V_n that is valid for any $n \ge 2$.

• Prove by induction on n that $V_n \le 3^{n}$.

6.

• How many permutations of the letters {a,b,c,d,e,f,g,h} are there?

• How many permutations of {a,b,c,d,e,f,g,h} are there that don't contain the letters ``bad'' (appearing consecutively)?

• 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?

• 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.)

7.

Suppose a biased coin with probability 3/4 of coming up heads is tossed independently 100 times.

• What is the conditional probability that the first 50 tosses are heads given that the total number of heads is 50?
• What is the expected number of heads?
• 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?

8.

A lake contains n trout. 100 of them are caught, tagged and returned to the lake. Later another set of 100 trout are caught, selected independently from the first 100.

• Write an expression (in n) for the probability that of the second 100 trout caught, there are exactly 7 tagged ones.
• Now consider selecting the second 100 trout with replacement. That is, you repeat 100 times the following steps: select at random a trout in the lake, check if the trout is tagged and return it to the lake before selecting a new trout. What is the probability that exactly 7 of the selected trout are tagged?

9.

At a casino, a two-ball version of roulette is played. Players place their bets as in the regular roulette, and collect winnings for each of the balls, e.g., if a player bets on red, and only one ball lands on red, he breaks even; if both balls land on red he wins his bet, and if none of the balls lands on red, he loses his bet.

There are 18 red, 18 black and two green numbers in roulette. We assume that in the two-ball roulette the two balls cannot land on the same number, but they are equally likely to land on any pair of distinct numbers. For simplicity, assume that players only bet on red or black.

• What is the probability of winning, losing and breaking even?
• What is the expected winning on a single $100 bet on red?
• What is the expected winnings on 100 $2 bets on red?

10.

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.

11.

Consider the 5 letter words over an alphabet of 26 letters.

• How many different 5 letter words (not necessarily meaningful) are there?
• We now consider two words to be equivalent if they are permutations of each other. For example, ``asdfa'' is equivalent to ``dsfaa''. How many such equivalence classes of words are there?

12.

A pitcher's record is 21 wins and 4 losses. Prove that he must have enjoyed a winning streak of 5 games.

13.

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?

14.

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?