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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ May the trees be along the border of the rectangle, where their roots would extend 5 m (or more) outside of it? $\endgroup$– humnCommented Sep 9, 2017 at 16:19
-
$\begingroup$ yes, the trees can be on the border $\endgroup$– DattierCommented Sep 9, 2017 at 16:26
-
$\begingroup$ 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. $\endgroup$– Rubio ♦Commented Oct 2, 2017 at 5:22
-
$\begingroup$ There is no justification for optimality @Rubio $\endgroup$– DattierCommented Oct 2, 2017 at 10:02
-
$\begingroup$ 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. $\endgroup$– Gareth McCaughan ♦Commented Oct 27, 2017 at 13:06
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
5
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:
-
$\begingroup$ it is difficult to justify that the proposed solution is optimal. I wait to see if nobody does better. $\endgroup$– DattierCommented Sep 9, 2017 at 18:11
-
$\begingroup$ @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. $\endgroup$– OrayCommented Sep 9, 2017 at 18:12
-
4$\begingroup$ @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. $\endgroup$ Commented Sep 9, 2017 at 19:31
-
$\begingroup$ I don't have an answer, but I know a very slow method, for find it. $\endgroup$– DattierCommented Sep 9, 2017 at 21:11
-
$\begingroup$ 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. $\endgroup$– SteveCommented May 26, 2020 at 6:39
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ thanks :) glad to have software answer for this. $\endgroup$– OrayCommented May 23, 2020 at 20:28
-
$\begingroup$ Circle packing density $\pi/(2\sqrt 3)$ implies an upper bound of $\lfloor (60\cdot 110)/(5^2 \cdot 2 \sqrt 3)\rfloor=76$. $\endgroup$– RobPrattCommented May 24, 2020 at 0:21
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ Have you looked at Oray's answer? It contains more trees than 50. $\endgroup$ Commented Sep 9, 2017 at 23:08
-
$\begingroup$ The OP has clarified that trees may indeed be planted at the border. $\endgroup$– Rosie FCommented Sep 12, 2017 at 7:20