2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is there some limit to a single step? Otherwise we can take any acceptable walk and magnify it to make a longer path. $\endgroup$ Jan 19, 2020 at 14:13
  • $\begingroup$ Oh, with longest I meant the most points, I'll edit the question to make that more clear $\endgroup$
    – Kasper
    Jan 19, 2020 at 14:15

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Very cool! Do you think this is optimal? $\endgroup$
    – Kasper
    Jan 19, 2020 at 17:49
  • $\begingroup$ I'm not sure. I've been trying to find a trick using the second dimension to up this score but without success so far. $\endgroup$
    – user502266
    Jan 19, 2020 at 17:58
  • $\begingroup$ Specifically, imagine a regular 12-gon A,B, ... , L and centre O. Can one tweak the position of the points so that there is a walk OACOEGO...OIKOLBODFO ... HJ followed by a path around the 12-gon? $\endgroup$
    – user502266
    Jan 19, 2020 at 19:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .