Orchard-Planting Problem
The orchard-planting problem (also known as the orchard problem or tree-planting problem) asks that 
trees be planted
so that there will be 
straight
rows with 
trees in each row. The problem of finding
the maximum number of lines of three points for 
points is due to
Sylvester (Croft et al. 1991, p. 159). The following table gives 
for various 
and 
.
 | 3 | 4 | 5 |
| Sloane | A003035 | A006065 | A008997 |
| 3 | 1 | -- | -- |
| 4 | 1 | 1 | -- |
| 5 | 2 | 1 | 1 |
| 6 | 4 | 1 | 1 |
| 7 | 6 | 2 | 1 |
| 8 | 7 | 2 | 1 |
| 9 | 10 | 3 | 2 |
| 10 | 12 | 5 | 2 |
| 11 | 16 | 6 | 2 |
| 12 | 19 | 7 | 3 |
| 13 | ![[22,24]](/images/equations/Orchard-PlantingProblem/Inline9.gif) |  | 3 |
| 14 | ![[26,27]](/images/equations/Orchard-PlantingProblem/Inline11.gif) |  | 4 |
| 15 | ![[31,32]](/images/equations/Orchard-PlantingProblem/Inline13.gif) |  |  |
| 16 | 37 |  |  |
| 17 | ![[40,42]](/images/equations/Orchard-PlantingProblem/Inline18.gif) |  |  |
| 18 | ![[46,48]](/images/equations/Orchard-PlantingProblem/Inline21.gif) |  |  |
| 19 | ![[52,54]](/images/equations/Orchard-PlantingProblem/Inline24.gif) |  |  |
| 20 | ![[57,60]](/images/equations/Orchard-PlantingProblem/Inline27.gif) |  |  |
| 21 | ![[64,67]](/images/equations/Orchard-PlantingProblem/Inline30.gif) | | |
| 22 | ![[70,73]](/images/equations/Orchard-PlantingProblem/Inline31.gif) | | |
| 23 | ![[77,81]](/images/equations/Orchard-PlantingProblem/Inline32.gif) | | |
| 24 | ![[85,88]](/images/equations/Orchard-PlantingProblem/Inline33.gif) | | |
| 25 | ![[92,96]](/images/equations/Orchard-PlantingProblem/Inline34.gif) | | |
Sylvester showed that
 |
(1)
|
where 
is the floor
function (Ball and Coxeter 1987). Burr et al. (1974) have shown using
cubic curves that
 |
(2)
|
except for 
, 11, 16, and 19, and conjecture that
the inequality is an equality with the exception of the preceding cases. For 
,
![r(k=3)<=|_1/3[1/2n(n-1)-[3/7n]]_|,](/images/equations/Orchard-PlantingProblem/NumberedEquation3.gif) |
(3)
|
where ![[x]](/images/equations/Orchard-PlantingProblem/Inline38.gif)
is the ceiling
function.
SEE ALSO: Configuration,
Euclid's Orchard,
Orchard Visibility Problem,
Sylvester's Line Problem,
Visible
Point
REFERENCES:
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 104-105 and 129,
1987.
Burr, S. A. "Planting Trees." In The Mathematical Gardner (Ed. David Klarner). Boston, MA: Prindle, Weber, and
Schmidt, pp. 90-99, 1981.
Burr, S. A.; Grünbaum, B.; and Sloane, N. J. A. "The Orchard
Problem." Geom. Dedicata. 2, 397-424, 1974.
Croft, H. T.; Falconer, K. J.; and Guy, R. K. Unsolved
Problems in Geometry. New York: Springer-Verlag, p. 159, 1991.
Dudeney, H. E. Problem 435 in 536
Puzzles & Curious Problems. New York: Scribner, 1967.
Dudeney, H. E. The Canterbury Puzzles and Other Curious Problems, 7th ed. London: Thomas Nelson
and Sons, p. 175, 1949.
Dudeney, H. E. §213 in Amusements
in Mathematics. New York: Dover, 1970.
Friedman, E. "Tree Planting Problems." https://www.stetson.edu/~efriedma/trees/.
Gardner, M. Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American.
New York: Vintage Books, pp. 18-20 and 26, 1977.
Gardner, M. "Tree-Plant Problems." Ch. 22 in Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman,
pp. 277-290, 1988.
Grünbaum, B. "New Views on Some Old Questions of Combinatorial Geometry."
Teorie Combin. 1, 451-468, 1976.
Grünbaum, B. and Sloane, N. J. A. "The Orchard Problem."
Geom. Dedic. 2, 397-424, 1974.
Jackson, J. Rational Amusements for Winter Evenings, Or, A Collection of Above 200 Curious and Interesting
Puzzles and Paradoxes Relating to Arithmetic, Geometry, Geography, &c. with Their
Solutions, and Four Plates, Designed Chiefly for Young Persons. London: J.
and A. Arch, 1821.
Macmillan, R. H. "An Old Problem." Math. Gaz. 30, 109,
1946.
Sloane, N. J. A. Sequences A003035/M0982, A006065/M0290, and A008997
in "The On-Line Encyclopedia of Integer Sequences."
Sloane, N. J. A. and Plouffe, S. Figure M0982 in The
Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.
Referenced on Wolfram|Alpha:
Orchard-Planting Problem
CITE THIS AS:
Weisstein, Eric W. "Orchard-Planting Problem."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Orchard-PlantingProblem.html
Contact the MathWorld Team
5-ary Lyndon words of length 12
