Orchard-Planting Problem
The orchard-planting problem (also known as the orchard problem or tree-planting problem) asks that n trees be planted so that there will be r(n,k) straight rows with k trees in each row. The problem of finding the maximum number of lines of three points for n points is due to Sylvester (Croft et al. 1991, p. 159). The following table gives max_(k)(r(n,k)) for various k and n.
Sylvester showed that
| r(k=3)>=|_1/6(n-1)(n-2)_|, |
(1)
|
where |_x_| is the floor function (Ball and Coxeter 1987). Burr et al. (1974) have shown using cubic curves that
| r(k=3)>=1+|_1/6n(n-3)_|, |
(2)
|
except for n=7, 11, 16, and 19, and conjecture that the inequality is an equality with the exception of the preceding cases. For n>=4,
| r(k=3)<=|_1/3[1/2n(n-1)-[3/7n]]_|, |
(3)
|
where [x] is the ceiling function.
See also
Configuration, Euclid's Orchard, Grünbaum-Rigby Configuration, Orchard Visibility Problem, Sylvester's Line Problem, Visible PointExplore with Wolfram|Alpha
More things to try:
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." http://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 ProblemCite this as:
Weisstein, Eric W. "Orchard-Planting Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Orchard-PlantingProblem.html