Newsgroups: alt.radio.networks.npr, rec.puzzles
Followup-To: rec.puzzles
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 20 Jan 1995 20:18:07 GMT
Subject: Re: WE puzzler for 1-15-95 [spoiler]

Richard Renner <rren...@igc.apc.org> writes:
> NPR Puzzler for January 15, 1995:
...
> The puzzle for next week comes from Sam Lloyd, a puzzler creator
> from the turn of the century.  It asks for the shortest route for
> a letter carrier through a certain town.  This town has three (3)
> east-west streets and four (4) north-south streets.  These streets
> make a total of seventeen (17) blocks in the downtown area.  For
> reasons created only in puzzles, the letter carrier can only make
> right turns.  Letter carrier must deliver to all the homes on all
> blocks.  So as the letter carrier approaches each intersection, only
> straight ahead and right turn are available.  The letter carrier
> covers both sides of the street while walking each block.  While
> starting from and ending at a place of your choosing, what is the
> shortest route?

A pretty good paraphrase.  You didn't mention that the postman serves
both sides of the street as he walks along each block.

Solution follows:

Paraphrased from the letter I mailed in to Liane and Will:

  The answer to the puzzle is that the postman must walk at
  least nineteen blocks, walking two of the blocks twice.  To see
  that this is the minimum distance, we may ignore for a moment the
  restriction on turns.  There are six three-way intersections, and
  each must be an endpoint of the postman's path or of a duplicated
  section.  So there must be at least two duplicated sections
  between three-way intersections.  Fortunately, there exist two
  pairs of three-way intersections one block apart, so the two
  duplicated sections can be one block each.  By starting at the
  three-way on the east or west side and ending up at the other, the
  postman can cover all the blocks in a large number of ways, dupli-
  cating only the middle north block and the middle south block.

  The requirement that the postman make no left turns reduces the
  number of solutions to three (up to symmetry).  The postman must go
  straight at every four-way intersection and must turn at every
  two-way intersection.  Starting at the west side heading north, he
  should turn right either
        at the 5th, 6th, 7th, 8th, and 10th,
        at the 2nd, 3rd, 5th, 6th, 8th, and 9th,
     or at the 2nd, 3rd, 4th, 5th, and 10th
  three-way intersection he goes through, as shown below.
     _________________      ________ ________       ________ ________
    |      _____      |    |      __X__      |     |      __X__      |
    |    6|     |7    |    |    9|     |2    |     |    5|     |2    |
    ^     |     |     |    ^     |     |     |     ^     |     |     |
     _____|_____|____ |     _____|_____|_____       _____|_____|____ |
  10|     |     |     |   5|     |     |     |6  10|     |     |     |
    |     |     |     |    |     |     |     |     |     |     |     |
    |    5|__ __|8    |    |    8|__ __|3    |     |    4|_____|3    |
    |________X________|    |________X________|     |_________________|

  I'm very glad that they posed a puzzle in logic and reasoning.
  It is much more satisfying than the vocabulary and trivia puzzles.
  I hope they can someday find a way to set an on-air puzzle composed
  of such problems.

If you look at the solutions, it's interesting to note that the there
are essentially two parts to the town: the inner loop, consisting
of the middle two north-south streets and the central block of the
outside east-west streets, and the outer loop, consisting of the
east-west streets and the outer north-south streets.  Transfers
between the two loops occur where they overlap, and the distinction
between the solutions is whether the postman takes the north transfer,
the south transfer, or both.

Perhaps I should also mention that this is one of those puzzles for
which writing a computer program is the wrong solution.  Solving it
by hand is both easier and more informative.

Dan
Hoey@AIC.NRL.Navy.Mil