Land claim staking

Question

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$.

Answer 1

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?".

Answer 2

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.