Standoff
Alex and Bob stand apart from each other in a square lattice,
points long in each dimension. Alex stands at the point
, and Bob stands at the point
. They're both looking to triumph over the other, but there's a small handicap - each gunner can only shoot vertically and horizontally,
Alex moves first, taking a single, 1 unit step, either in a horizontal direction, or a vertical direction, positive or negative. He must take a step (he cannot 'pass' his turn), and he cannot leave the bounds of the lattice, . If he steps into the same row or column as Bob, though, he'll lose, because Bob will be ready to gun him down, and will get the first shot off.
Bob moves second, under the same constraints, and likewise, if he steps into the same row or column as Alex, he'll lose. Both players continue taking turns in this manner until the game ends.
Assume Alex and Bob play perfectly. What will be the outcome of the game?
Given: Alex and Bob both have perfect information at all times. They know all of the rules in the above paragraphs, and they always know where both players are positioned at the start of every turn.
Image Credit: http://www.aprilniemela.com/?p=317
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Notice that the taxicab distance between Alex and Bob is always even at the start of Alex's turn, and always odd at the start of Bob's turn. Since each step flips the parity of the taxicab distance, this condition is invariant at all stages of the game.
When the distance is odd, and ≥ 3 , Bob can always reduce the distance between Alex and himself along at least one dimension, without putting himself in Alex's line of fire. If he does this every turn, since Alex doesn't have infinite room to backpedal, he will eventually be at a distance 2 from Alex at the end of his turn, positioned diagonally down and to the left of him.
Alex then has no choice but to step further away, up or to the right. Bob can mimic this move, putting them back at distance 2 , over and over, until Alex is backed into the corner at ( 1 0 0 , 1 0 0 ) , with Bob at ( 9 9 , 9 9 ) , at the end of Bob's and the start of Alex's turn. Alex only has two valid moves from this position, and for each one, Bob wins.
Since Alex's moves have no power to hinder this strategy, Bob always wins.