Security Guard

A security guard guards a grid of north-south and east-west paths around a bunch of cargo crates in neat lines and rows. He does a patrol route occasionally, subject to two rules;
a. he ends the route where he started;
b. he doesn't follow the same path twice.

So, if he has just one crate to guard, he walks north-east-south-west. Zero unguarded paths.

a 2 x 1 area is harder. north-east-east-south-west-west, one path is left unguarded.

2 x 2 might start at the middle; north-east-south-west-south-west-north-east. Or at a corner, 2N 2E 2S 2W, or some other route, but four paths are left unguarded.

So.. how many roads at left unguarded if the guard uses an optimal route around m lines x n rows of crates?

Can't he see down the paths?

Number of paths = n(m+1) +m(n+1)
Let number of paths = p

Using Pick's Theorem:
where A = area;
i = inner dots;
b = outer dots = 2(m+n) or the perimeter (it works in this case since it is a rectangle; plus all squares are rectangles);

Pick's Theorem is A = i + b/2 - 1
m*n = i + (m+n) - 1
i = m*n - (m+n) + 1

total dots = i + b
Let total dots = d

In this case unguarded pathways is the same as inner pathways (call it u).

u = p - (d-i)


In terms of m and n:

u = n(m+1) +m(n+1) - ( (m*n - (m+n) + 1) + 2(m+n)) - (m*n - (m+n) + 1))


NB
The outer dots are the same as the perimeter in this case.

Originally posted by damionhonegan
Number of paths = n(m+1) +m(n+1)
Let number of paths = p

Using Pick's Theorem:
where A = area;
i = inner dots;
b = outer dots = 2(m+n) or the perimeter (it works in this case since it is a rectangle; plus all squares are rectangles);

Pick's Theorem is A = i + b/2 - 1
m*n = i + (m+n) - 1
i = m*n - (m+n) + 1

total dots = i + b
Let total ...[text shortened]... m+n)) - (m*n - (m+n) + 1))


NB
The outer dots are the same as the perimeter in this case.

I did that when I was tired.

The answer is simply the number of paths subtracted by the perimeter.


ungguarded paths = n(m+1) +m(n+1) - 2(m+n)

Let m<=n. If either m or n are even I think the answer is m+n. If both m and n are odd or m=1, m+n-2.

The corners all have 2 paths, the middle all have 4 paths, those on the perimeter but not on the corner have 3 paths. The problem occurs on the outer perimeter where three paths lead from an intersection (bridges of konigsberg type problem). So for every pair of three path intersections a path is left unguarded. So for an mxn grid there are 2(m-1) + 2(n-1) three paths. So halving this leaves m+n-2 unguarded paths.

However this solution works when m and n are odd (leaving an even number of paths not patrolled). In the case where m and n are odd you are forced to lose 2 corner paths on opposite corners which leaves m+n. In the case of m being odd and n being odd you lose 2 paths from adjacent corners again being m+n.

The one final case is where m=1. In this case you can walk around the outside and pair off the opposite awkward 3 junctions. This will be n-1 unguarded (equal to m+n-2 so no need to introduce yet a new formula).