1
$\begingroup$

A prisoner has escaped from the maximum security prison in puzzlevania! Apparently, the prison's security system - which was composed of guards who either always tell the truth or lie and doors with lions behind them - proved insufficient for her mastery of paradoxes (which, mind you, was how she got in there in the first place). The police would really like to get her back, but they're having trouble because she's way less lazy than they are. Thankfully, the chase obeys a very strict set of rules and so is easily to analyze:

The chase takes place in a series of discrete turns on an $a\times b$ grid of squares. Each turn, first, the fugitive can make any number (i.e. zero or more) of moves left, right, up or down, so long as no move brings her in the same square as a police officer. Then, a single police officer may make a single move to an adjacent unoccupied square. The police can only capture the fugitive if they surround her completely, leaving her no legal moves. Moves may "wrap around" the edges of the board, so one may move upwards from the top row and end up on the bottom row, and similarly for left and right rows. (For the mathematically minded, that means this board is a torus)

In particular, this chase takes place on a $a\times b$ board with $3\leq a\leq b$. At the start, there are $2a$ police officers distributed randomly across the board and the fugitive is allowed to choose their position from any available one (after seeing the arrangement of the police).

Can the police ensure the capture of the fugitive? How?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Can they just make two columns of a officers and slowly collapse inward, or am I missing something? $\endgroup$
    – xnor
    Dec 31, 2015 at 23:00
  • $\begingroup$ @xnor I was hoping that'd be a little less obvious. But yeah, basically. (There is a bit more to say about showing that they can actually move into a suitable arrangement even with the fugitive's interference, but it's more or less trivial) $\endgroup$
    – Milo Brandt
    Dec 31, 2015 at 23:03

1 Answer 1

Reset to default
5
$\begingroup$

The police can capture her.

The police forms 2 lines of length A. The prisoner can't cross the line since she can't move diagonally. If one line is stationary, and the other line (1 officer at a time) advances the line, eventually the prisoner will be stuck between the two lines.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.