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 '17 at 16:19
• yes, the trees can be on the border – Dattier Sep 9 '17 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 '17 at 5:22
• There is no justification for optimality @Rubio – Dattier Oct 2 '17 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. – Gareth McCaughan Oct 27 '17 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. – Dattier Sep 9 '17 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 '17 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. – Mike Earnest Sep 9 '17 at 19:31
• I don't have an answer, but I know a very slow method, for find it. – Dattier Sep 9 '17 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. – Steve May 26 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.

• thanks :) glad to have software answer for this. – Oray May 23 at 20:28
• Circle packing density $\pi/(2\sqrt 3)$ implies an upper bound of $\lfloor (60\cdot 110)/(5^2 \cdot 2 \sqrt 3)\rfloor=76$. – RobPratt May 24 at 0:21

50, all centered within an equidistant grid marked out at 10m intervals. No trees should be planted on the border/s, as any good farmer knows the fruit falling on his neighbors' property is lost, so, grid off the 50/100 field at 10 m intervals, center the trees within each square avoiding the property lines.

• Have you looked at Oray's answer? It contains more trees than 50. – boboquack Sep 9 '17 at 23:08
• The OP has clarified that trees may indeed be planted at the border. – Rosie F Sep 12 '17 at 7:20