Problem: Dot Connection (Karl Scherer)
It is known that when n>=3, then n*n point of an n x n lattice can be
connected by 2n-2 straight lines drawn without lifting the pencil from
the paper. Prove that 2n-2 lines are necessary or provide a counterexample.


Problem: Dot Connection II (Karl Scherer)
Connect the seventeen dots in the figure with six straight lines 
without lifting the pencil from the paper. There are two solutions.

    o   o
  o o o o o
    o o o
  o o o o o
    o   o

Problem: Constellation (Serhiy Grabarchuk)
Connect the thirteen dots in the figure with five straight lines 
without lifting the pencil from the paper. There are three solutions.

      o
    o o o
  o o o o o
    o o o
      o





- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Solution: Dot Connection
This was solved by Selfridge in 1955.


Solution: Constellation
There are three solutions with the turning points on the grid.

      . 2
      o .
    o o 6
  3 o o o 4
    1 o o
    . o
    5 .


  5 . 3
  . o o o
  1 o o o 2
    o o 6
      o
      .
      4


5 .
. . . 3
  . o o o
  1 o o o 2
    o o 6
      o
      4


Rererences:

- Murray S. Klamkin;
  American Mathematical Monthly 61 (June 1954) 423 proposal by Klamkin
  American Mathematical Monthly 62 (Feb. 1955) 124 solution (sufficient) by Klamkin
  American Mathematical Monthly 62 (June 1955) 443 solution (necessary) by Selfridge
  - connect n x n lattice points by 2(n-1) line.
  
- Ed Pegg;
  Connect the dots - Arcs,
  Connect the dots - Lines,
  http://www.mathpuzzle.com/dots.html
  - connect n x m lattice points by lines or circular arcs.

- Ed Pegg;
  Constellation
  http://www.mathpuzzle.com/constellation.htm
  - connect the points by 5 lines.

- Karl Scherer;
  Problem 820: Dot Connection,
  Journal of Recreational Mathematics 12 (1980) 55 (problem)
  Journal of Recreational Mathematics 13 (1981) 71 (problem)

- Karl Scherer;
  Problem 989: Dot Connection II,
  Journal of Recreational Mathematics 13 (1981) 220 (problem)
  Journal of Recreational Mathematics 14 (1982) 232, 320 (solution)
  http://karl.kiwi.gen.nz/prdots1.html (problem on Karl's page)

- Fred. Schuh;
  The Master Book of Mathematical Recreations,
  Dover Publ. 1968,
  - Chapter 14.2 Broken Lines through Dots (Sections 272-275)
  - solutions for the 3x3, 3x4 and 4x4 point arrangements.

- Charles W. Trigg;
  Mathematical Quickies,
  New York 1967, (reprint: Dover Publ., 1985)
  - Q 261. Polygonal Path in a Lattice
    show that 2n-2 lines are sufficient to connect the point 
    of an n x n lattice.
    M. S. Klamkin, AMM 62 (Feb. 1955) 124

- euler.free.fr/dots/
  - solutions for the 3x4 and 4x4 point arrangements.

--
http://www.mathematik.uni-bielefeld.de/~sillke/
mailto:Torsten.Sillke@uni-bielefeld.de