Longest possible walk between points on a plane such that the distance between points strictly decreases

66 Views Asked by At

Pick $n$ points on a plane. Now perform a walk on this plane, starting from an arbitrary point, such that the distance between any two consecutive points of the walk strictly decreases. It is allowed to revisit an earlier point. What is the longest possible walk you can devise, measured by the number of steps taken?

I think I have a lower bound at $3n / 2$. Consider a central point $C$ and two points $X$ and $Y$ on a line, such that $|CX| = 1$, $|XY| = 2/3$, $|YC| = 1/3$. Now scale down the line segments $CX$ and $CY$ by a factor 10, let's call the new points $X'$ and $Y'$. The path $C \to X \to Y \to C \to X' \to Y' \to C \to \dots$ satisfies the condition. This process of scaling can be repeated as many times as we want. In the resulting path, $C$ is revisited once for every 2 other points, for a total of about $n + (n-1)/2 + 1 \approx 3n/2$ steps in total.

I conjecture $2n$ is an upper bound, as it doesn't seem possible to revisit almost every point more than once, but I cannot prove it.

1

There are 1 best solutions below

3
On BEST ANSWER

Your method can be adapted to achieve more steps than $3n/2$.

If we think of your $CXY$ configuration as 'standard', then construct the following series of such configurations:-

$$CXY, YCU, UYV, ...$$

Then adding each new point creates two further steps. In total we have $2n-3$ steps.