First we set some shorthand. Let Dy be the distribution specified in the first bullet of Step 2. Specifically, Dy draws (x1,,xk){0,1}nk, sets (y1,,yk)=F(x1,,xk){0,1}mk; then chooses i[k] and overwrites yi with y, outputting (y1,,yk). Also, let us say that A(y1,,yk) wins if A returns (x1,,xk){0,1}nk such that F(x1,,xk)=(y1,,yk). Finally, we say that y{0,1}m is bad, and write yBAD, if PrDy[A(y1,,yk) wins ]/k. Problem 5. Complete the proof that Pr[B inverts y]>1 by doing the following. (a) Prove that if y/BAD then Pr[B inverts y]=12(n). Deduce that it suffices to show that Pry{0,1}m[y/BAD]>1/2. (b) Prove that Pr(y1,,yk){0,1}mk[A(y1,,yk) wins \& i st yiBAD]. Deduce that Pry{0,1}m[y/BAD]k. (c) Complete the proof by showing that if Pry{0,1}m[y/BAD]1/2, then 2n, a contradiction since is non-negligible