5
$\begingroup$

It was traditional during the times of the Oregon Trail and the gold rush that men founding new towns were allowed to stake their claim on land upon arriving to the west coast.

Suppose a man is given $n$ minutes to stake his claim on an area of land defined by the convex hull of those stakes placed into the ground.

For simplicity, assume the man travels 1 kilometer in 1 minute and assume there are no obstructions of any kind and that the land is completely flat. Also, assume an unlimited amount of stakes available.

  1. Assuming that it takes no time to plant a stake into the ground, what is the optimal strategy for maximizing land area for stakes placed in this way?
  2. Supposing it takes $m$ minutes to plant a stake, how does this change the optimal strategy (where $0 < m < n$)?
  3. Assume the man is told he is given a fixed amount of time (you can assume that it takes no time to plant a stake into the ground as in scenario #1), but he is not told how long, how does this affect the optimal strategy for maximizing land area?

Edit: Rephrasing scenario #3 for clarity. What would be the best strategy such that $\sum\limits_{i=1}^n f(i)$ is optimized where $f(i)$ is the area given maximum amount of time $i$.

$\endgroup$
  • $\begingroup$ What is probability distribution of "unknown amount of time" in option 3.? $\endgroup$ – klm123 Jul 15 '14 at 13:08
  • $\begingroup$ @klm123 Hmm, it shouldn't matter. I have difficulty expressing what I mean by "optimal strategy", because obviously if you knew how much time you had, you'd do better than someone following a more generic strategy not knowing how much time he had. I suppose the best way to put it would be the best average area for any given n. Obviously the best strategy for $n$ won't be the best general strategy. $\endgroup$ – Neil Jul 15 '14 at 13:10
  • $\begingroup$ it must matter. Consider distributions A) with 100% probability that $t=1$ and 0$ probability that $t \notequal 1$and b) 100% probability that $t=100$. $\endgroup$ – klm123 Jul 15 '14 at 13:12
  • $\begingroup$ @klm123 Assume it is equally distributed from 3 to $\infty$ $\endgroup$ – Neil Jul 15 '14 at 13:15
  • 1
    $\begingroup$ @Neil, that's impossible. math.stackexchange.com/q/255667/5676 $\endgroup$ – Peter Taylor Jul 15 '14 at 13:18
2
$\begingroup$

It is clear that the area must be a polygon with stakes at corners.

I do not have prove, but most probably:

  1. The fastest way to put stake it each corner is to follow perimeter of the polygon. So we must optimise an area between the path and a line (which goes through first and last stake). The maximum area is given by semicircle. (It is the shape of soap bubble put on a table, physical lows there optimise area of the bubble with given volume, which is virtually what we need). The aria would be $S = \pi(\frac{n}{\pi})^2 = n^2/\pi$.

  2. We should use regular polygon here with some number of corners $k$. But we must follow only half of it, similarly to semicircle (thanks kaine for insight on this). So side of polygon must be $A = (n-k/2\cdot m)/(k/2) = 2n/k-m$. The area of half polygon would be $S = 1/8(2n/k-m)^2cot(180/k)$. One needs to find derivative and assign it to zero to find the maximum. Unfortunately I can't do it without computer, but what have to be done is quite clear, may be some one else would like to do it.

  3. Here the strategy must depend strongly on probability distribution of the given time $t$, which is not given [Here I talk about initial formulation of the question, now it is changed].
    For standard uniform distribution from 0 to $T_{max}$, I don't know how to approach it strictly, but the wild guess would be to use logarithmic spiral, like in the task "What is quickest way out from forest, if you lost?".

$\endgroup$
  • 1
    $\begingroup$ You don't need to follow the full perimeter of the polygon: you can skip the final edge, because the convex hull takes care of it. The result is still that a circle is optimal, but it's not a direct appeal to the well-known result that it's the shape that maximises area for a fixed perimeter. $\endgroup$ – Peter Taylor Jul 15 '14 at 13:09
  • 1
    $\begingroup$ @PeterTaylor, oh.. thanks. Circle would not be optimal then I think... semicircle may be. $\endgroup$ – klm123 Jul 15 '14 at 13:10
  • $\begingroup$ Actually I was just coming to the same conclusion. $\endgroup$ – Peter Taylor Jul 15 '14 at 13:11
3
$\begingroup$

Klm123 is largely right but I am hoping to add to it. Obviously, the path he follows must remain on the perimeter of the shape or he is wasting running time.

1) A semicircle is correct. Circles have the largest ratio of area to perimeter. The semi-circle takes advantage of the longest straight line so he doesn't have to run it.

2) A regular polygon with $2x$ sides approximates a circle with the same radius as the polygons apothem. $x$ is the number of stakes he places assuming there was already one at the start. $$A=\frac{(n-xm)^2}{4x \tan(\pi/2x)}$$ The derivative of this is too complex for wolfram to calculate the maximum for a general case but $x$ tends to be very small even if $m$ is low as they cause a relatively small improvement.

3) If he does not know how long he has, his strategy whilst constantly placing stakes is to maximize the derivative of the area with time. Assume that he starts going in the $y$ direction on a parametric graph where $x$ is a function of $t$ describing his location perpendicular to his starting direction and $f(x)$ is his. (For ease f(x) is he same as y(x).) Lets say at any given time he is going in the direction $\phi$ relative to these axes at a given time: $$\frac{\partial A}{\partial t}=\frac{x(y+y')-y(x+x')}{2}=\frac{xy'-yx'}{2}=\frac{x \sin(\phi)-y \cos(\phi)}{2}$$ $$\frac{\partial^2 A}{\partial t \partial \phi}=\frac{x \cos(\phi)+y \sin(\phi)}{2}=0$$ $$\tan(\phi)=\frac{-x}{y}$$

This winds up making a spiral once we state that a zig zag is unacceptable. I am not satisfied with a spiral as that yields locations where he is wasting running time by covering the same area several times.

As this is inherently an attempt to create a curve where the final line approaches being perpendicular to the first, a line along $f(x)=e^x$ seems to be very appropriate. He traps 227km after walking 100km. Proving that is optimum...I can't seem to find a way to do that one way or he other.

$\endgroup$
  • $\begingroup$ I am not sure what you meant exactly in 2), but reading it and 1) gave me insight, this must be half-poligon similarly to semicircle. Do you mean it here? $\endgroup$ – klm123 Jul 15 '14 at 19:38
  • $\begingroup$ Yes, the equation for a polygon in 2 approximates a semicircle. I thought that part was well developed by then found a math error. $\endgroup$ – kaine Jul 15 '14 at 19:41
  • $\begingroup$ @kaine You're correct for point 1. Optimal area is a semicircle. However, point 2 is really the same problem except planting infinite stakes is not possible, so it is a polygon optimizing the semicircle shape (as you've figured out, requires a derivative to determine the best mix). For point 3, while it's true a spiral would be retracing over old area, if it distanced itself enough, I imagine it would still be better than $f(x) = e^x$, though I also can't prove it. $\endgroup$ – Neil Jul 16 '14 at 7:39
  • $\begingroup$ @Niel I agree with you sentiments on parts 1 and 2. The issue with a spiral is the rate at which it wraps around. If you let it wrap about 6 times, you may only cover 28km. If, however, It never makes half a loop, you approach the efficiency of a semmicircle. I think there is something better than both but haven't come up with it yet. $\endgroup$ – kaine Jul 16 '14 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.