Define A(t) to be the treasure in the first t rooms of the other path.
The problem is to prove that G(n) is at least half as great as A(n), where n is the number of layers of the dungeon. Do you see why?
If you could prove that G(t) is at least half as large as A(t) for all t, you would of course be done. You should try to prove that by induction, but don't spend too much time, because that is the wrong approach.
The purpose of asking you to try induction is to convince you that it is the wrong approach, and so that you will have a better appreciation of the complexity of the problem.

Back to Assignment Page
Back to Assignment 1