Induction problem 5


Without loss of generality, suppose that we always go clockwise around the path.

Also notice that starting on an empty stretch of path is the same as starting right at the next object. And it is clearly futile to start at a monster. So we can assume that we start right at the location of some energy cube.

Proof by induction on n, which is the number of monsters in the game.

Base: At n=1, we have one monster and one energy cube. So you can win the game by starting at the location of the single energy cube.

Inductive hypothesis: Suppose that we can pick a starting point that will let us win the game, for any arrangement of n monsters and n cubes, where n ranges from 1 to k-1.

Rest of the inductive step: Suppose we have a game G with k monsters and k cubes.

Moving clockwise around the path for G, find an energy cube c that immediately precedes a monster m. Suppose we remove both c and m from the game. This gives us a new game G'.

G' has only k-1 monsters and k-1 cubes. So, by the inductive hypothesis, we can win the game by starting at some cube p in G'.

Now, start at cube p in game G. Between p and c, we're seeing the same sequence of objects as in game G'. That is, we have defeated all the monsters so far and we are carrying t spare energy cubes. After eating cube c and defeating monster m, we again have t spare energy cubes. So we can continue as in game G'. So we have found a starting point (p) that will let us win the original game G.


Is your proof mostly talking about features of the game, e.g. monsters and paths and cubes? It's ok to incorporate some equations, but they should be related back to the original problem.