Hint for Problem 8 on the final exam. Pick a large number N. (Say, N = 1000.) Draw the opt-graph. (It will have 2N+1 nodes, one for each reachable offset function.) Draw the red-black graph. (It will have 4n+2 nodes, one for each pair (omega,s) where omega is a reachable offset function and s is either A or B.) There will be no red arrows, but each arrow will have a black cost and a red cost. From each node, there draw the arrow showing what happens if A is requested and what happens if B is requested. In some cases, where WFA allows two choices, there will be an extra arrow. For each node in the red-black graph, define the "lazy potential" of that node to be the maximum red cost of any path whose black cost is zero and which starts from that node. For each arrow where the black cost is positive, prove that the inequality holds, where C = 2. Make sure your logic works regardless of the value of N. Then, you're done. As N gets larger, the formulas look more complicated. But as N goes to infinity, the formulas converge to simple formulas. Write it down.