1 Stencil the flea There is a small flea named Stencil. To his right, there is an endless flat plateau. One inch to his left is the Cliff of Doom, which drops to a raging sea filled with flea-eating monsters Cliff of doom

Problem 1. A couple decides to have children until they have both a boy and a girl. What is the expected number of children that they'll end up with? Assume that each child is equally likely to be a boy or a girl and genders are mutually independent Solution. There are many ways to solve

Problem 1. Suppose that you flip three fair mutually independent coins. Define the fol- lowing events: Let be the event that the first coin is heads. · Let be the event that the second coin is heads. · Let be the event that the third coin is heads

This is a good approach to questions of the form, What is the probability that ntuition will mislead you, but this formal approach gives the right answer every time 1. Find the sample space. ( Use a tree diagram. 2. Define events of interest. Mark leaves corresponding to these events 3. Determine outcome probabilities (a) Assign edge probabilities

Notes for Recitation 14 Counting Rules Rule 1(Generalized Product Rule). Let be a set of length-k sequences. If there are: n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. then:

Notes for Recitation 13 Basic Counting Notions bijection or bijective function is function:x→ such that every element of the codomain is related to exactly one element of the domain. Here is an example of a bijection:

An explorer is trying to reach the Holy Grail, which she believes is located in a desert shrine d days walk from the nearest oasis. In the desert heat, the explorer must drink continuously. She can carry at most 1 gallon of water, which is enough for 1 day. However, she is free to create water caches out in the desert. For example, if the shrine were 2/3 of day's walk into the desert, then she could recover

1 Bipartite Graphs Graphs that are 2-colorable are important enough to merit a special name; they are called bipartite graphs. Suppose that G is bipartite. Then we can color every vertex in G ei ther black or white so that adjacent vertices get different colors. Then we can put all the

1 Graphs and Trees The following two definitions of a tree are equivalent Definition 1: A tree is an acyclic graph of n vertices that has n-1 edges Definition 2: A tree is a connected graph such that Vu, v E V, there is a unique path connecting u to u. In general, when we want to show the equivalence of two definitions, we must show

Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural