TOPICS
Search

Orchard-Planting Problem

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.

n\k345
OEISA003035A006065A008997
31----
411--
5211
6411
7621
8721
91032
101252
111662
121973
13[22,24]>=93
14[26,27]>=104
15[31,32]>=12>=6
1637>=15>=6
17[40,42]>=15>=7
18[46,48]>=18>=9
19[52,54]>=19>=10
20[57,60]>=23>=11
21[64,67]
22[70,73]
23[77,81]
24[85,88]
25[92,96]

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

Subject classifications