Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member talzamir
    Art, not a Toil
    15 Jul '12 18:46
    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?
  2. Subscriber AThousandYoung
    Proud Boys Beware
    18 Jul '12 03:12
    Can't he see down the paths?
  3. 20 Jul '12 08:23 / 3 edits
    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.
  4. 20 Jul '12 16:27
    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)
  5. Subscriber deriver69
    Keeps
    24 Jul '12 05:03 / 1 edit
    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).