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?
Asked
Active
Viewed 792 times
5
-
May the trees be along the border of the rectangle, where their roots would extend 5 m (or more) outside of it? – humn Sep 09 '17 at 16:19
-
yes, the trees can be on the border – Dattier Sep 09 '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 02 '17 at 05:22
-
There is no justification for optimality @Rubio – Dattier Oct 02 '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
-
This problem is closely related to the one discussed here where you will see that the biggest proven-optimal case has n=36. – Gareth McCaughan Oct 27 '17 at 13:08
-
@GarethMcCaughan but there is a very slow solution, if anyone give it, that's closed the problem – Dattier Oct 27 '17 at 16:09
3 Answers
10
I believe the answer is
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 extraonetwo trees to put in your farm compared to standard way of putting trees!
Here is the best answer:
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:
Oray
- 30,307
- 6
- 61
- 215
-
it is difficult to justify that the proposed solution is optimal. I wait to see if nobody does better. – Dattier Sep 09 '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 09 '17 at 18:12
-
4@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 09 '17 at 19:31
-
-
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 '20 at 06:39
7
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<j\le 68$} \end{align} 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.
RobPratt
- 13,685
- 1
- 29
- 56
-
2
-
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 '20 at 00:21
1
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.
user40672
- 11
- 1