Orchard-Planting Problem (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

OrchardProblem

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]]|, ](http://mathworld.wolfram.com/images/equations/Orchard-PlantingProblem/NumberedEquation3.svg) | (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 Point

Explore with Wolfram|Alpha

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. SequencesA003035/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

Subject classifications