# The farmer and the olive trees

A farmer has a rectangular ground of 100 m by 50 m, he wants to plant olive trees, in sufficiently spaced ways (to avoid exhaustion by the roots) at least 10 meters from each other.

How much can one hope to put at the most, effectively?

• May the trees be along the border of the rectangle, where their roots would extend 5 m (or more) outside of it?
– humn
Sep 9, 2017 at 16:19
• yes, the trees can be on the border Sep 9, 2017 at 16:26
• Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful.
– Rubio
Oct 2, 2017 at 5:22
• There is no justification for optimality @Rubio Oct 2, 2017 at 10:02
• Proving optimality for this sort of problem is notoriously difficult. I think a few very small cases have been solved rigorously, but none as large as this one. Oct 27, 2017 at 13:06

67 $68$

as shown in the flower kind figure below (This is the previous answer):

The idea behind this is

Starting to plant from the left and the right at the same time to the right, you will lose one tree every 1.8 meters as you see in the figure but gain 0.1 meter compared to putting trees all the corners etc. So after 10 trees, you will have an extra 6 tree to put as you see on the right side of the flower graph even though you lose 1 tree every 1.8 meters. At the end you will able to get extra onetwo trees to put in your farm compared to standard way of putting trees!

The main difference is actually starting from left and the right, after completing one vertical plantation, go for the next from the furthest point to the area in the farm

as you will see below:

• it is difficult to justify that the proposed solution is optimal. I wait to see if nobody does better. Sep 9, 2017 at 18:11
• @Dattier it has to be optimal since I have started from the very beginning of the rectangle and move to the with the least area covering from left to right. Though I may not able to show it mathematically.
– Oray
Sep 9, 2017 at 18:12
• @Dattier If you are asking for an optimal solution, you should know how to prove the answer is optimal. I think it would be better to ask "How can you plant x trees?", without worrying about whether x is optimal. At the very least, you should say up front that you do not know for sure what the optimal answer is. Sep 9, 2017 at 19:31
• I don't have an answer, but I know a very slow method, for find it. Sep 9, 2017 at 21:11
• To improve the visualisation, draw the circle around each tree at HALF the minimum distance to the next tree, then rather than overlapping by up to 1 radius creating a "flower kind figure", minimally-spaced trees would have circles that just touch, creating a circle packing solution - i.e. similar to the answer to a different problem that you linked here from yesterday. May 26, 2020 at 6:39

As in my answer to My Mother's Dish Collection, I used a nonlinear optimization solver, with variables $$x_i$$, $$y_i$$ to represent the coordinates of the trees. The constraints are: \begin{align} 0 \le x_i &\le 100 &&\text{for i\in\{1,\dots,68\}}\\ 0 \le y_i &\le 50 &&\text{for i\in\{1,\dots,68\}}\\ (x_i - x_j)^2 + (y_i - y_j)^2 &\ge 10^2 &&\text{for 1\le i The first two constraints make sure each tree is contained in the rectangle, and the third constraint enforces a distance of at least 10 between trees.

The resulting $$x$$ and $$y$$ coordinates returned by the solver are essentially the same as @Oray's packing.

The solver was not able to find a feasible solution for 69 trees, but I have no proof that 68 is the maximum.

• Circle packing density $\pi/(2\sqrt 3)$ implies an upper bound of $\lfloor (60\cdot 110)/(5^2 \cdot 2 \sqrt 3)\rfloor=76$. May 24, 2020 at 0:21