Induction problem 5


The problem has strongly hinted at what your induction variable should be, i.e. how you should measure the size of each game.

Think about taking a game of size k and removing something to get a game of similar structure but size k-1. What general sort of thing(s) do you need to remove?

To pin down exactly which thing(s) to remove, think about how you need the inductive step to work. The inductive hypothesis will give you a solution to the smaller game. Then you need to modify this into a solution for the bigger game.