14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "There is a very strict law that says that there may not be more than two criminals at a time", so why do we only need to consider one target? Also am I right in thinking that during the initial setup criminals will not remain in the cells in which the new force are placed? $\endgroup$ – Jonathan Allan Jun 2 '16 at 5:18
  • 1
    $\begingroup$ @JonathanAllan Oops, that was a typo; the law reads that there may not be more than one criminal at a time. I have corrected this. The criminals in this society are very well behaved, so will, rather than all escaping at once, escape one at a time. $\endgroup$ – Milo Brandt Jun 2 '16 at 5:21
  • $\begingroup$ +1 for the creative story-wrapping. I think it can be assumed, but maybe state somewhere that movements are for 4-connectivity not 8-connectivity unless diagonal moves are allowed? $\endgroup$ – BmyGuest Jun 2 '16 at 5:37
  • 2
    $\begingroup$ "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." .... And of course criminals are know to adhere to laws all the time... $\endgroup$ – BmyGuest Jun 2 '16 at 5:38
4
$\begingroup$

The correct answer is:

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

This can be shown using the following figures:

Even:
Even
Odd:
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.
3D torus

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.

$\endgroup$
  • $\begingroup$ Awesome. +1 That's me dead then? ...Then again, if this is how they budget for crime, my execution shouldn't be too much to worry about. $\endgroup$ – Brent Hackers Jun 2 '16 at 10:17
  • $\begingroup$ Well your answer with 2 parallel lines works for both odd and even situation, but as you can see with odd you can do 1 better. $\endgroup$ – Bas Jun 2 '16 at 11:57
  • $\begingroup$ So there's a 50/50 chance I live. $\endgroup$ – Brent Hackers Jun 2 '16 at 12:01
  • $\begingroup$ 2n is more than necessary for even n. $\endgroup$ – Ben Frankel Jun 2 '16 at 16:52
  • $\begingroup$ I don't see a way for the criminal to evade in the "partial" solution by @BenFrankel, so long as we move the cardboard coppers in the right way (his 'corners' left or right first and then keeping no gaps to close the walls in for odd and his 'middles' first up or down... for even) $\endgroup$ – Jonathan Allan Jun 2 '16 at 16:53
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The sides of the city wrap around, so one can't split the city across the diagonal - this is what I meant by saying that the city is like a torus. That is, if the cops make the diagonal and start pushing in, the criminal would just walk out the bottom of the city to the top of the city. $\endgroup$ – Milo Brandt Jun 2 '16 at 1:49
  • $\begingroup$ @MiloBrandt Oops, I completely forgot about that. $\endgroup$ – Ben Frankel Jun 2 '16 at 1:50
  • 1
    $\begingroup$ Only possible problem I see is resetting after catching the first criminal, could a crafty crook evade indefinitely by occupying cells in which we wish to place a cardboard copper for our reset? $\endgroup$ – Jonathan Allan Jun 2 '16 at 17:00
  • $\begingroup$ Your solution for even $n$ doesn't look like it'd work. The top and bottom corners of the square are the same cop, so if you try to crush the square by moving the bottom cop up, you also move the top cop up, which releases the criminal from the square. $\endgroup$ – Milo Brandt Jun 2 '16 at 17:35
  • $\begingroup$ @MiloBrandt Right, but we're not moving anything up, just moving the right wall left and/or the left wall right. EDIT: Nevermind, the same is true for the left and right corners of the square... $\endgroup$ – Ben Frankel Jun 2 '16 at 17:36
2
$\begingroup$

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:enter image description here

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.

$\endgroup$
  • $\begingroup$ I don't see how this works. You haven't actually split the area into multiple parts. $\endgroup$ – Kruga Jun 2 '16 at 7:52
  • $\begingroup$ The image is just a reference, i have two such 'bands' on opposing ends. $\endgroup$ – Tim Couwelier Jun 4 '16 at 14:39
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I had the exact same idea, but you beat me while I was typing out a more elaborate explanation :) $\endgroup$ – Tim Couwelier Jun 2 '16 at 6:57
  • $\begingroup$ I kept it concise for that very reason. Love the use of a picture in yours. +1 $\endgroup$ – Brent Hackers Jun 2 '16 at 6:58
  • 1
    $\begingroup$ I received a message from the mayor of Frugalia in light of this answer, which suggests too many policemen. He says to tell you that you are to appear in court at the judge's next earliest convenience to be tried for conspiracy to waste money. Given the judicial system's large backlog and severe understaffing, your trial will probably occur in 50 - 100 years. $\endgroup$ – Milo Brandt Jun 2 '16 at 18:12
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice try, but the question says "Frugalia is a city made of a n×n grid of cells, each cell connected to its 4x4 neighbors, with the edges wrapping around top to bottom and left to right to make a torus. $\endgroup$ – Deusovi Jul 21 '16 at 18:30
  • $\begingroup$ -1: missed the main point of the puzzle. $\endgroup$ – Nij Jul 22 '16 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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