Frugality 101: How to Replace Your Police Force with Cardboard Cutouts

Question

In the far away land of Frugalia - a land where the conservation of money has been elevated to the status of any of Newton's laws - a conundrum is being had. There has been an upsurge in citizens breaking the law: They are buying lottery tickets, paying taxes, choosing higher end products, and otherwise not saving money. A long time ago, such deeds were handled by the police, who were authorized to use lethal force on such scofflaws. However, as of late, changes to the national budget have caused the police to dwindle to just a single officer.

The brilliant economic strategists of Frugalia have come up with a solution: The police force will be supplemented with an army of cardboard cutouts in police uniforms, meant to function very much like scarecrows for criminals. This has been an immensely popular proposal, since people believe it can lower crime rates while costing far less than a traditional police force.

Obviously, the Frugalians wish to purchase as few cardboard policeman as possible, in order to save money. The remaining policeman has the following to say about what the police force must necessarily do:

As we all know, Frugalia is a city made of a $n\times n$ grid of cells, each cell connected to its $4$ neighbors, with the edges wrapping around top to bottom and left to right to make a torus. There is a very strict law that says that there may not be more than one criminal at a time, so we only need to consider having one target for a police chase.

As I am only paid to work $1$ minute a day, I can only do so much in a chase: Each day, I will move one cardboard policeman to an adjacent cell not occupied by either the criminal or another cardboard policeman. Thankfully, due to our network of low quality CCTV cameras, I will always be aware of where the criminal is.

Between my movements, the criminal can make as many moves between adjacent cells as they wish, so long as they never occupy the same cell as a cardboard police officer. That is, they are free to move in any connected portion of the city in which there are no officers. They will surrender to arrest if they are ever surrounded on all four sides.

The town has announced that, despite its frugal nature, it will award a generous bounty of one upvote and the associated 10 imaginary internet points to any individual who can determine the minimum number of cardboard cops that the town needs to ensure the eventual capture of any criminals. Of course - needless to say - the penalty for advising the town to buy more cardboard policeman than is necessary is death, as the wasting of money is a capital offense in Frugalia.

Answer 1

The correct answer is:

2n for even n
and 2n-1 for odd n

This can be shown using the following figures:

Even:

Odd:

Explanation

The crosses in both figures divide the torus in two equal sized shapes, which both are completely enclosed. Since both are identical it does not matter in which one the culprit is, and from these figures it is easy to see how this trap can be enclosed step by step.

3D visualisation:

With the carboard police officers in white and the 2 different area's in black and gray. This is a visualisation of an torus odd n where you can see that intersection in the back consists of a 2x2 block while the intersection in the front is a single officer. The 2x2 block can freely move in any direction with connecting both areas and thus making the area the bad guy is in smaller.
For n is even, with 2n officers both intersections would a 2x2 block as can be seen in the 2D-images.


Addendum: The 3D images shows why a police force of 2n-2 for even n would not be sufficient. In that case, both intersections would consist of a single officer. Moving this (or any other) officer in any direction would merge both area's.

I haven't found a way yet to prove that a smaller sized cardboard police force is not possible, however for every possible smaller configuration I could think of a way for the offender to evade the police indefinitely so far.

P.S. This is my first answer, so feel free to update my answer for better formatting etc.

Answer 2

Not yet a solution, just progress.

$2n-1$ for odd $n$ is a sufficient quantity of cardboard cops.

The cop's strategy: Start with all the cardboard cops in an X shape, splitting the city into left+right and top+bottom halves. Assume WLOG that the criminal is in the top+bottom half. Imagine that we want to turn this (*) into the more claustrophobic this, and so on, until the criminal is trapped. We can do this because we always have a double threat: the left wall and the right wall.

(*) Here Black is interpreted as a cardboard cop, Orange is the same thing but translated to show that it's a torus, and Red is the criminal.

EDIT: Removed claim that $2n-2$ is sufficient for even $n$, because my attempt was flawed.

---

EDIT: The below is only true when the city is NOT a torus--which it is.

$n$ is the necessary and sufficient quantity of cardboard cops.

Necessary (the criminal will win if there's fewer than $n$)

The criminal's strategy: Pick a corner of the city and just sit there, until a move exists that would cut off the criminal's connection to the majority of the city. When that is the situation, hop to any other corner. This strategy will always work because it is impossible with fewer than $n$ cardboard cops to threaten to cut off all of the corners simultaneously, and it is impossible to "gradually" turn a majority area into a minority area because fewer than $n$ cops cannot cut the city exactly in half.

Sufficient (the cop will win if there's $n$)

The cop's strategy: Start with all the cardboard cops along the main diagonal, splitting the city into top right and bottom left halves. Assume WLOG that the criminal is in the bottom left. We have 2 objectives (while keeping in mind that the criminal must remain fenced in at all times): push the top left cardboard cop down, and push the bottom right cardboard cop left. At any point, the criminal can only prevent progress in one of these objectives, so we can just make progress in the other. With two walls closing in, eventually one of the cops will reach the bottom left corner and we will have the criminal surrounded on an edge. At this point it's very easy to push the cops into the necessary formation.

Answer 3

Best idea I have for now:

2n cardboard cops

How to place them:

Start out by creating two 'rings' on the torus, on opposing sides, and each of the rings looks like this:

How to move them:

We know all movement is strictly 'adjacent', so no diagonals are made. This means that by moving the elements of one of the rings to whichever side CCTV says the bandit is on, in n days we can move the ring by one grid space, without ever creating a gap that lets the bandit 'escape' into the bigger part. Repeat until enclosed area no longer allows movement, rendering the bandit trapped.

Addition for sneaky bandits:

Should, at one point, the bandit be aware of this, and remain halted someone on the line you're trying to move.. switch to moving the other line instead, and work from two sides, each times moving in from the side the bandit is not at.

Answer 4

I will probably die of bad mathematics but- assuming that the police officer can't stand in for a cardboard cutout because he's not paid to work all day, wouldn't the answer be n+n? So that he can prop up 2 paralel lines around the world and have them close in gradually on the criminal?

Answer 5

I believe the answer should just be n. Because Frugalia is a square, n cops could create a straight line from one end to the other, in either direction. By lining up in a straight line, the cops would be able to March towards a criminal, without him passing them, resulting in his eventual capture.