Solution to "The Lineup Puzzle"

Solution 1: If you start with a 3 by 3 square that has 8 lines, you can easily modify it to create 10 lines by sliding the four corner points left and right. Now we have 3 horizontal lines, 1 vertical, and the 2 diagonals; we've lost two vertical lines, but we've gained 4 new lines that join the corner points, an endpoint of the middle row, and the middle of the top or bottom row.

Here is a table based on Gruenbaum, giving the number of trees, and the maximum number of rows of 3 that can be produced. Values which are not known to be the best have a question mark.

Number of trees	Rows of 3
3	1
4	1
5	2
6	4
7	6
8	7
9	10
10	12
11	16
12	19
13	22?
14	26?
15	31?
16	37
17	40?
18	46?
19	52?
20	57?

Solution 2: you can arrange 10 pennies into 5 rows of 4 by placing them in a star pattern:

 
              *

        *   *   *   *

           *     *
              *
          *       *
      

Solution 3: you can arrange 16 points in such a way that there are 15 lines of 4 points [Dudeney]. To do this, place three nested pentagons around a center point. The first pentagon can be of arbitrary size, but symmetric about the center point. To determine the second one, draw a star inside the first pentagon; this star will circumscribe the second pentagon. Draw a star inside the second pentagon to determine the third pentagon. The 16 points then comprise the vertices of the three pentagons, and the center point.

Here is a table based on Gruenbaum, giving the number of trees, and the maximum number of rows of 4 that can be produced. The values are known to be the best possible through N = 12.

Number of trees	Rows of 4
4	1
5	1
6	1
7	2
8	2
9	3
10	5
11	6
12	7
13	9?
14	10?
15	12?
16	15?
17	15?
18	18?
19	19?
20	21?
21	23?

Here is a table based on Gruenbaum, giving the number of trees, and the maximum number of rows of 5 that can be produced. Most of these results have not been proven to be maximal.

Number of trees	Rows of 5
5	1
6	1
7	1
8	1
9	2
10	2
11	2
12	3
13	3
14	4
15	6
16	6
17	7
18	9
19	10
20	11
35	36

Reference 1:

Pierre Berloquin,
100 Geometric Games.

Reference 2:

Henry Dudeney,
Amusements in Mathematics,
Originally published in 1917.

Reference 3:

Martin Gardner,
Tree-Plant Problems,
Time Travel and Other Mathematical Bewilderments,
Freeman, 1988.

Reference 4:

Branko Gruenbaum,
New Views on Some Old Questions of Combinatorial Geometry,
Teorie Combinatorie,
Volume 1, 1976, pages 451-468.

Back to the The Lineup Puzzle.