Orchard-Planting Problem

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

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

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

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

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$,

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

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.