1. Define an assignment of n balls to m bins to be "smooth" if every bin has at most 2 ceiling(n/m) balls in it. Given m, for approximately what range(s) of n is there at least a 50% probability that n balls thrown into m bins will be smooth?

2. Prove that, for almost all graphs drawn from the G(n,1/2) distribution, every vertex is within distance two of every other vertex. (Here, "almost all" means "with probability that goes to zero as n goes to infinity". Hint: use Markov's inequality on the expected number of pairs that are not at distance two.)

3. Recall that a random regular graph is with high probability an expander graph, meaning that for some constant c, with high probability, every subset S of the vertices of the graph has at least (c/n) |S| |V\S| neighbors, where V\S is the complementary set to S. Prove from this property that every two vertices are at distance at most O(log n) from each other.