info prev up next book cdrom email home

Orchard-Planting Problem

\begin{figure}\begin{center}\BoxedEPSF{OrchardProblem.epsf}\end{center}\end{figure}

Also known as the Tree-Planting Problem. Plant $n$ trees so that there will be $r$ straight rows with $k$ trees in each row. The following table gives max($r$) for various $k$. $k=3$ is Sloane's A003035 and $k=4$ is Sloane's A006065.

$n$ $k=3$ $k=4$ $k=5$
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]$ $\geq 9$ 3
14 $[26, 27]$ $\geq 10$ 4
15 $[31, 32]$ $\geq 12$ $\geq 6$
16 37 $\geq 15$ $\geq 6$
17 $[40, 42]$ $\geq 15$ $\geq 7$
18 $[46, 48]$ $\geq 18$ $\geq 9$
19 $[52, 54]$ $\geq 19$ $\geq 10$
20 $[57, 60]$ $\geq 21$ $\geq 11$
21 $[64, 67]$    
22 $[70, 73]$    
23 $[77, 81]$    
24 $[85, 88]$    
25 $[92, 96]$    

Sylvester showed that

\begin{displaymath}
r(k=3)\geq\left\lfloor{{\textstyle{1\over 6}}(n-1)(n-2)}\right\rfloor ,
\end{displaymath}

where $\left\lfloor{x}\right\rfloor $ is the Floor Function (Ball and Coxeter 1987). Burr, Grünbaum and Sloane (1974) have shown using cubic curves that

\begin{displaymath}
r(k=3) \leq 1+\left\lfloor{{\textstyle{1\over 6}} n(n-3)}\right\rfloor ,
\end{displaymath}

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\geq 4$,

\begin{displaymath}
r(k=3)\geq \left\lfloor{{\textstyle{1\over 3}}[{\textstyle{1...
...\lceil{{\textstyle{3\over 7}} n}\right\rceil ]}\right\rfloor ,
\end{displaymath}

where $\left\lceil{x}\right\rceil $ is the Ceiling Function.

See also Orchard Visibility Problem


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.

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.

Gardner, M. Ch. 2 in Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. New York: Vintage Books, 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. London, 1821.

Macmillan, R. H. ``An Old Problem.'' Math. Gaz. 30, 109, 1946.

Sloane, N. J. A. Sequences A006065/M0290 and A003035/M0982 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26