Thursday, January 19, 2012

Nab the thief-prove that Alice can win in at most 3n moves.

Alice and Bob play the following game: Two cops(c) and a thief(t) are positioned at some vertices of an nxn grid. Alice controls the two cops and Bob controls the thief. The players take turns to play, starting with Alice. In one turn, Alice can move each cop to a neighboring vertex, i.e. left, right, up or down or keep the cop in the same place. In his turn, Bob can move the thief similarly.
If the thief and a cop end up in the same vertex, Alice wins.
For any arbitrary positioning of the two cops and the thief, prove that Alice can win in at most 3n moves.