Devise a continuous path that visits each * exactly once:

geometry/hamilton.path New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Devise a continuous path that visits each * exactly once:

         /*   *\
       / / \ / \ \
      | *   *   * |
      |  \ / \ /  |
      |   *   *   |
       \ / \ / \ /
        *   *   *
         \ / \ /
          *   *
         / \ / \
        *   *   *
       / \ / \ / \
      |   *   *   |
      |  / \ / \  |
      | *   *   * |
       \ \ / \ / /
         \*   */

-- Bryan Boswell <bryan_boswell@hp.com>, "Continuous Path?"

Show solution

It is not possible.  Consider:

         /A   A\
       / / \ / \ \
      | *   *   * |
      |  \ / \ /  |
      |   A   A   |
       \ / \ / \ /
        *   *   *
         \ / \ /
          A   A
         / \ / \
        *   *   *
       / \ / \ / \
      |   A   A   |
      |  / \ / \  |
      | *   *   * |
       \ \ / \ / /
         \A   A/

Every path must alternate ...A*A*A*A...

But every finite path of this form has at most a difference of 1
between the number of A's and the number of *'s.  As there are 10 A's
and 12 *'s in the original diagram, no finite path hits all vertices
exactly once.

-- Wei-Hwa Huang <whuang@ugcs.caltech.edu>