Arrange 10 points so that they form 5 rows of 4 each.

Additional material

[ Editor: the puzzle was posed in 1997 as "How do you arrange 10
diamonds into 5 rows of four diamonds?", and Thomas Brooks answered
"Put them in the shape of a 5 pointed star." ]

That's one solution.  The remaining infinite number of solutions
can be obtained by drawing 5 arbitrary nonparallel lines no more
than two of which intersect at any given point, then placing the
diamonds in those intersections.

-- Risto Lankinen <rlankine@us.oracle.com>

lynnj@netcom.com (Lynn Johannesen) writes:

> That's the one most people think of.  In fact there are 12
> topologically distinct answers.  ObPuzzle:  find the rest.
> (The problem is analyzed in detail in Dudeney's _Amusements
> in Mathematics_.)

[ Editor: the entry above says there are three topologically unique
answers; Johannesen's figure of 12 is reported here as he gave it. ]

It's not THAT hard.  Draw 5 lines, no two of which are parallel.  Placing
a diamond at the intersection points yields a solution to the original
problem.  Take any solution to the original problem and draw a line
through each row of 4.  This yields 5 mutually non-parallel lines. Thus,
finding all topologically distinct solutions is equivalent to finding all
distinct ways of drawing 5 lines no two of which are parallel.  There is
only one topologically distinct way of drawing 3 lines, no two of which
are parallel.  Suppose we have a particular drawing of 3 mutually
non-parallel lines labeled A, B, and C.  How many topologically distinct
ways can we add one line that intersects all three?  Surprisingly, only
one.  Consider the triangle formed by the intersection of A, B, and C.
There are only two possibilities; the 4'th line either intersects two
edges of this triangle or it doesn't intersect any edges of the triangle.
Both of these are topologically equivalent (draw the picture and see!).
How many ways are there to add a 5'th line that intersects all 4 of the
other lines?  I see several immediately.  I'll let somebody else count
them as I don't have the time right now.

-- Glenn C. Rhoads <rhoads@paul.rutgers.edu>

[ Editor: Rhoads's equivalence assumes, as Lankinen states, that no
three of the five lines pass through one point; with three concurrent
lines the five lines have fewer than ten intersection points. ]

[ Editor: Dan Hoey replied to a posting of this puzzle, criticizing the
archive's (older, one-line) star solution as neither the only solution
nor a demonstration of optimality. ]

On demonstrating optimality, boy@ss.titech.ac.jp (Sermsak Uatrongjit)
starts a fair job of a proof: Numbering the (first five) lines L0, L1,
L2, L3, and L4, then line Li can have at most i points in common with
previous lines, and so introduces at least 4-i new points.  This is an
upper bound, too, since that number will include all ten points.
Unfortunately, he finishes abruptly with ``we cannot construct any
line furthur since it will cause overlap.''  He offers no
justification for the last statement, and I see no simple way of
proving it.

My method of proving optimality is first to consider the case that
three of the lines meet at a point.  Those three lines contain three
new points each, so all ten points occur on those three lines.  Any
line of four in the arrangement must then include two points from one
of the three lines, and so must coincide with that line.  So at most
three lines can be formed in this way.  In the other case, if at most
two lines meet at each point, then each point will be in line with at
most six other points.  This adds up to at most 60 ordered pairs of
distinct points in the lines; using them up at twelve pairs per line
means we can only have five lines.

Now for finding a solution: Finding solutions is in a sense easier
than finding non-solutions.  Pick five lines at random.  Unless you
hit the probability-zero jackpot, each pair of lines will intersect in
a different point, making ten points, QEC.  But a star need not occur,
as in the following two configurations:

                 *
                / \
               /   \        *.------*---*-------.*
              /     \         `.     \ /      ,'
             *.     ,*          `.    *     ,'
            /  `. ,'  \           `. / \  ,'
           /    ,*.    \            *. ,*'
          *---,*---*.---*          / ,*. \
         /  ,'       `.  \        /,'   `.\
        / ,'           `. \      *'       `*
       /,'               `.\
      *'                   `*

For an ObPuzzle, characterize the shapes of possible solutions, with
proof.

The FAQ and the previous respondent are not alone in offering barely
adequate solutions, though.  _Lewis Carroll's Games and Puzzles_ from
Dover offers a case where Alice has ten tiny cakes in a two-by-five
rectangular array.  By moving four of them she is to form five rows of
four.  Carroll mentions, ``There is more than one solution to this
problem.  See if you can find other solutions.''

Only one solution is listed, and it is mentioned that ``other
solutions use the possibility of stacking cakes on top of one
another.''  I see no way of making such an attack work, and I don't
think it is at all what Carroll had in mind.  An Obpuzzle is to (1)
characterize, and (2) count, the ways of moving four of the cakes to
other locations in the plane so as to make five rows of four.  Treat
the cakes as points, and no making rows of more than four.

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>