# Journey with integer steps

I remember today a problem that I first hear probably 12 years ago:

Suppose that a walker starts a journey at the point $A$ in $\mathbb{R}^2$. The first day, the walker travels a distance of $M$ km ($M\in\mathbb{N}\setminus\{0\}$) and stops for the day. In the next days, the walker travels each day 1 km more that the previous day, in a different direction that the previous day, and then stops.

Question: Will the walker ever come back to the starting point? Namely, is there a path with the above conditions that ends in $(0,0)$ after an integer number $n$ of days?

For instance, I know that this problem could have solutions if the distance covered the first day is 3 km (using a Pythagorean triple $(3,4,5)$), but I don't know how to get other solutions, or even if consider $M\in\mathbb{R}$ will also be interesting.

I also don't know if this is an easy or difficult question, or if it is related with a much more difficult problem. Does anyone know how to solve this problem? or a similar one?

Post-edition: Thanks to @ChristianBlatter we know now that the answer is positive if you admit any point as a stop point. But what happen if you require furthermore that the stop points must have integer coordinates?

• I think you mean to add the condition that each stop must be on a point with integer coordinates. If not, then there's clearly a solution for every $n > 3$ as well since you can draw an $n$-gon with sides $1, 2, \ldots , n$. – Ethan Bolker Mar 29 '16 at 13:11
• Probably I would like to add that condition. However, I still don't see clearly that one can draw an $n$-gon with sides $1,2,\ldots,n$ for $n>3$. – Darío G Mar 29 '16 at 13:18
• If you connect $n>3$ sticks with those lengths end to end at their corners with the angles free to take on any values it's clear you can arrange them so that the chain ends where it began. Triangles are rigid, but just imagine how flexible a quadrilateral is even with edge lengths fixed. – Ethan Bolker Mar 29 '16 at 13:34
• @mercio I am afraid you are thinking that every day the direction is different from all previous days, but actually the condition is that the direction on one day is different from the immediately previous day. Therefore, you can pleasently walk on the grid of $\mathbb{Z}^2$. – Darío G Mar 30 '16 at 9:15

For example, when $n=8$ the walker could go ($M$ is a positive integer):

$M$ East

$M+1$ North

$M+2$ West

$M+3$ South

$M+4$ West

$M+5$ South

$M+6$ East

$M+7$ North,

and that would bring the walker back home, while stopping only at intermediate points that have both coordinates integers.

This is not a full answer, but I don't have the reputation to comment yet. This problem immediately seems to be the study of intersections of circles in the plane. Whilst I can't answer in general, you can derive the (3,4,5) pythagorean triple answer using a method. \Say you want to return in 3 day, starting with a step of 3. On the first day you would end up somewhere on a circle, centred at the origin of radius 3, and on the start of the last day you require that you are on a circle of radius 5, origin centred. Without loss of generality you travel along the x-axis on day 1, and then draw a circle of radius 4 around (3,0). \The intersections of these three circles produces your known solution and proves it is the only solution on the criteria (3 days travel, starting M=3) • It is true that it is not a full answer. Rather you are proposing your idea for a solution. I still do not see how it would help to solve the problem, but I like this geometric point of view. – Darío G Mar 29 '16 at 12:55

We prove the existence of such closed walks inductively as follows:

With $(M,M+1,\ldots, M+n-1)$ we denote some admissible closed $n$-gon whose consecutive side lengths begin with $M\in{\mathbb N}_{\geq1}$.

You cannot produce an $(1,2,3)$, but you can produce an $(1,2,3,4)$ and $(M,M+1,M+2)$ for any $M\geq2$. Assume that you can do $(M,M+1,\ldots, M+n-1)$ for some $n\geq3$. You then can replace the last leg of length $M+n-1$ by two legs of length $M+n-1$ and $M+n$ respectively, and in this way obtain an $(M,\ldots,M+n)$.

• Yes, this solves the original question in $\mathbb{R}^2$, and I like the fact that it uses the intuition proposed by @King947. Do you know how to solve the more difficult problem of stop always in points with integer coordinates? – Darío G Mar 29 '16 at 13:44

If I'm not wrong the random walk with vertices:

-6,  -2,
-3,  -6,   len=5
-9,  -6,   len=6
-9, -13,   len=7
-1, -13,   len=8
-1, -22,   len=9
5, -14,   len=10
-6, -14,   len=11
-6,  -2,   len=12


fits the conditions of your edited question.

I don't have existence conditions, but, at least, we know the problem has solutions.

EDIT:

Maybe you'll like this journey, with lenghts from $1$ to $15$. • How did you calculate this walk? – Darío G Apr 4 '16 at 7:49
• When you want to draw a snake winding, python can help you! – N74 Apr 4 '16 at 21:07

Here's an intuitive "proof" that such a walk exists for any $n\ge 3$. Consider the sequence $k+1$, $k+2, \dotsc, k+n$. If we regard these as the side lengths of a convex $n$-gon, then as $k\to\infty$, this approaches a regular $n$-gon, so it is certainly plausible that such an $n$-gon exists, at least for some $k$ (that is, that it can be closed).

• I find a little bit suspicious that you regard $k+1,\ldots,k+n$ as the side lengths of a convex $n$-gon. Are you already thinking than the starting point will be equal to the ending point after the day $n$? I understand that you say that as $k\to\infty$ the sides are "almost the same", which probably means that you can do such a journey starting with $k$ kms on the first day and ending "very close" after $n$ days. However, I would like to end after $n$ days precisely at the starting point. – Darío G Mar 29 '16 at 13:15
• Here's another way to think about it. Start with a regular $n$-gon with side length $1000000n$. Clearly you can add $1$ to one side and you'll still have an $n$-gon. Then add $2$ to the next side, and so on. Since the result is so close to a regular $n$-gon (it's only off by about one part in a million), it's pretty clear (intuitively, again) that this is possible. – rogerl Mar 29 '16 at 15:56
• I think you are mentioning what is the problem: you will be off, probably by a very small quantity, but you will not get exactly to the starting point. I am far more convinced by the argument given by ChristianBlatter (and notice that you can construct the 4-gon using circles, assuming that the first day ends in the point $(1,0)$ and the last day ends in the point $(0,4)$. – Darío G Mar 29 '16 at 16:16