Orchard Planting Problem/Classic Form

Classic Problem

A given number $n$ of trees are to be planted in an orchard so as to make the number of rows of $3$ trees the largest number possible.

That is:

$n$ points are to be configured in the plane so that the number of straight lines that can be drawn through exactly $3$ of these points is maximised.

Solution

Let the maximum number of rows of $3$ for a given number of trees $n$ be denoted $t_3 \left({n}\right)$.

Then we have:

\(\ds t_3 \left({3}\right)\)

\(=\)

\(\ds 1\)

\(\ds t_3 \left({4}\right)\)

\(=\)

\(\ds 1\)

\(\ds t_3 \left({5}\right)\)

\(=\)

\(\ds 2\)

\(\ds t_3 \left({6}\right)\)

\(=\)

\(\ds 4\)

\(\ds t_3 \left({7}\right)\)

\(=\)

\(\ds 6\)

\(\ds t_3 \left({8}\right)\)

\(=\)

\(\ds 7\)

\(\ds t_3 \left({9}\right)\)

\(=\)

\(\ds 10\)

\(\ds t_3 \left({10}\right)\)

\(=\)

\(\ds 12\)

\(\ds t_3 \left({11}\right)\)

\(=\)

\(\ds 16\)

\(\ds t_3 \left({12}\right)\)

\(=\)

\(\ds 19\)

This sequence is A003035 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

$3$ Trees

The number of rows is $1$.

$\blacksquare$

$4$ Trees

The number of rows is $1$.

$\blacksquare$

$5$ Trees

The number of rows is $2$.

$\blacksquare$

$6$ Trees

The number of rows is $4$.

$\blacksquare$

$7$ Trees

The number of rows is $6$.

$\blacksquare$

$8$ Trees

The number of rows is $7$.

$\blacksquare$

$9$ Trees

The number of rows is $10$.

$\blacksquare$

$10$ Trees

The number of rows is $12$.

$\blacksquare$

$11$ Trees

The number of rows is $16$.

$\blacksquare$

$12$ Trees

The number of rows is $19$.

$3$ of the points are at infinity.

One of the $19$ rows is also at infinity, and passes through each of those $3$ points.

$\blacksquare$