Define A(t) to be the treasure in the first t rooms of the other path.
Let F(t) equal half G(t) minus A(t). Use a potential argument to prove that F(n) is nonnegative. Then, we are done. (Why?)
Back to Assignment Page
Back to Assignment 1