Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

Here is a little puzzle I invented. I think it is likely someone else has invented the same puzzle too, or at least explored a similar one. With that in mind, I'll explain it to you.

Suppose you are trapped in the origin of the two-dimensional Cartesian coordinate system. Wait, that sounds too exciting. Suppose you are just visiting. (You can leave any time. Go to some lovely non-Euclidean space or wherever.)

You are at the point (0,0). Now, you can travel into any of the four main directions and take a single unit length step. Then you have to change direction and take two unit length steps. And so on.

Just to make sure, the four main direction are towards the increasing y coordinates, and we can call this north, towards the decreasing y coordinates for south, increasing x for east and decreasing x for west. To keep it short, we can call these N, S, E and W. Because you can only move in these directions, you'll always end up in a spot that has integer coordinates.

Changing direction in this puzzle means turning exactly 90 degrees left or right. You have to do this after every single turn, which consists of taking multiple steps in a straight line. The number of steps is the increasing sequence 1,2,3,4 and so on. (Some guy called Peano knows all about this stuff. I think they were used before him, though.)

For example, suppose you start by going north. You end up at the position (0,1) after taking the single step you start with. Then you choose to go east, so you end up at (2,1) and then north again, for the final position of (2,4) after three moves of one, two and three steps, respectively. You could simply say that your travels started with turns NEN in this case.

So, the questions are, suppose you keep doing this: Will you ever find your way to the point (0,0) again? If you do find a way, can you do it so your path never intersects itself? This means you cannot ever again visit a spot again, except for the origin where you finally end up, making a nice little (or possibly big) loop.

(Since we're on a Drod forum, one could always consider an infinite field of trapdoors overlaid with orthosquares. You are standing on a single floor square in the middle of that field and suddenly decide you just have to take one step north, and you do so. Then you make two steps east or west, then three steps north and south and so on. Can you return to that original floor tile just making these kinds of moves?)

And to close this off, here are two slightly harder questions:

Is such a path possible if instead of using consecutive integers, you use the Fibonacci numbers? They start with 1,1,2,3,5,8... and the next number is always the sum of two previous ones.

What about the sequence of primes? If you make moves that consists of first 2, then 3, then 5 steps, and so on, taking the length from consecutive primes, can you again make a non-self-intersecting path that returns to the origin?

(And as a bonus question, can you think of any other sequence of integers that makes this puzzle particularly interesting?)

I found out that I could find solutions to all these questions that I am reasonably sure are not wrong using just pen and paper. However, if you write an interesting computer program, you could share it as well. Please remember to use secret tags for now, though, so as not to spoil the puzzle for others.

You can also present solutions in a form that has only letters L and R for left and right turns, respectively. It doesn't really matter in which direction you start off, since the problem is symmetrical. Just be sure to specify which integer sequence you are using.

Well, I hope you enjoy this easy little puzzle. I have some answers I can post later, if that is necessary.

Red-XIII
Level: Smitemaster

Rank Points: 623
Registered: 08-05-2012
IP: Logged

I LOVE IT! I found a solution for the easy sequence, 1-2-3-4...
I don't know if there are infinite solution but here's mine

Later I'll try the prime and Fibonacci sequence!

I love math!

____________________________
There's not some other world out there where everything's gonna be okay.
There's just this one, just this rock.
-33th Skywatcher

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

For the primes, I think this sequence returns to the origin, but I think it crosses itself:

NWNENESWSESWNWSEN

Here are the primes sorted by direction traveled:
N: 2, 5, 11, 41, 59
S: 17, 23, 31, 47

E: 7, 13, 29, 53
W: 3, 19, 37, 43


____________________________
Progress Quest Progress

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

I don't think a path that returns to the origin is possible with the Fibonacci sequence. For any n, let Fn be the nth Fib number (example: F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 etc).
F(2n) > F(2n-2) + F(2n-4) + F(2n-6) + ... F(2)
and
F(2n+1) > F(2n-1) + F(2n-3) + ... F(1)

So, F(2n) will be stepped in one direction (say north). Even if all the other even F(even numbers < 2n) are stepped in the opposite direction (south), they won't compensate for that one single step to the north. Since the F(odd numbers) have to be stepped east/west, they can't be used to make up the difference. So you'll never land on the x-axis, let alone the origin. Similarly for the odd Fib's in the E/W directions.

A similar argument can be applied to the sequence of powers of 2 (in fact, even if you relax the requirement that your steps have to be in the cardinal directions, the powers of 2 sequence can never return to the origin).

____________________________
Progress Quest Progress

---

[Last edited by stigant at 11-04-2012 09:45 PM]

Red-XIII
Level: Smitemaster

Rank Points: 623
Registered: 08-05-2012
IP: Logged

I was thinking that with Fibonacci sequence it was not possible but I wan't able to prove it by only saying that the Fibonacci sequence increase way too fast, that's a nice demonstration stigant!
About prime sequence I was trying that by considering also 1 as a prime number but I didn't do it yet; your solution is pretty long, that's cool!

____________________________
There's not some other world out there where everything's gonna be okay.
There's just this one, just this rock.
-33th Skywatcher

Someone Else
Level: Smitemaster

Rank Points: 1306
Registered: 06-14-2005
IP: Logged

How about the nth powers?

There are clearly sequences which this cannot be done to, where Stigant's test succeeds. (such as 2N = the sum of every even element - 1) So for which does this succeed? I would guess that it succeeds any time the previous condition is true and the sequence can be stated as a(n)=f(n), where f(n) is a rational function.

---

[Last edited by Someone Else at 11-05-2012 03:18 AM]

Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

File: stigants.png (11.8 KB)
Downloaded 359 times.
License: Public Domain

Thank you for your interest. Red-XIII found a good example of a path made from consecutive integers. It seems probably that there are in fact an infinite amount of solutions, but I have not proved this yet. Perhaps someone will take an interest in the other possible solutions and post something about it?

Stigant is right about the Fibonacci sequence not allowing a solution to this problem. I prepared my own argument based on the identity that the sum of all the values in the Fibonacci sequence to F(N) is equal to F(N+2)-1, which is easy to show with mathematical induction. The conclusion is the same of course. (Example of the identity with N = 4: 1+1+2+3 = 7 = 8 - 1 (skipping 5).)

I also drew a picture of the path that Stigant gave for the primes. It does indeed cross itself, so it is not a proper solution, but it does return to the origin all right.

It's a bit awkwardly sized. I should write a better script for creating these, because I've found a few bigger ones and they turn out to be kind of big. I won't post any of the others yet, so I'll leave it open if there is a non-crossing path and how big it is--but you should be able to settle it with pen and paper.

Image:

Someone Else
Level: Smitemaster

Rank Points: 1306
Registered: 06-14-2005
IP: Logged

I think it should be possible to prove that an infinite number of series can be made:

First, it is only possible whenever the length of the even series (n) is congruent to 3 or 0 mod 4. This is obvious because when dividing the sum of the series by 2 the result still needs to be even, and considering triangle numbers (2n(n-1)/2 = n(n-1)) is only divisible by 4 when n or n-1 is divisible by 4 (the other is odd).

It should also be obvious that this sum is always possible to make with the even half of the series; add the largest numbers possible until that sum equals the needed sum. You'll always have enough numbers and only have to add 2 last.

The odd sequence is a little harder.
Its length (N) can be n or n+1. So N = 0,1,3 mod 4. But in the odd series, there must be an even difference in the step length because (2a+1 + 2b+1 = 2c+1, 2(a+b)=2c+3, which is clearly impossible). So N is divisible by 4. As the first and last in the series equal the second and second last equal the third and third last, and so on, and there are an even number of these pairs, the odd sequence can also be evenly divided.

Therefore there are an infinite number of possible series of this sort formed by consecutive integers.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Someoneelse said:

There are clearly sequences which this cannot be done to, where Stigant's test succeeds. (such as 2N = the sum of every even element - 1) So for which does this succeed? I would guess that it succeeds any time the previous condition is true and the sequence can be stated as a(n)=f(n), where f(n) is a rational function.

an = 1/n^2 will never return since a1 = 1 > a2+a3+a4+... = pi^2/6 - 1. I'm not sure if your statement about my condition holds for that particular sequence (your phrasing is a little vague). This sequence fails for a similar but slightly different reason than the fib. sequence does. In this case, one element is greater than the sum of all the subsequent terms. In the Fib case, every element is greater than the sum of all the previous terms.

(Also, I realize the original formulation was for integer sequences, but Someoneelse explicitly suggested that rational sequences would work)



____________________________
Progress Quest Progress

---

[Last edited by stigant at 11-05-2012 04:52 PM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Oh, lol... it's easy to construct a sequence where no term is greater than a sum of the rest of the terms but can't return to the origin:

1, 1, 2, 2, 2, 2, 2, 2, 2, 2, ...



____________________________
Progress Quest Progress

Someone Else
Level: Smitemaster

Rank Points: 1306
Registered: 06-14-2005
IP: Logged

Ah, yes. I meant to apply it to polynomial functions with integer coefficients. Not sure what possessed me to say rational function.

I have found a solution for squares:

N 1 49 121 169
S 9 25 81 225
E 4 16 64 196
W 36 100 144

---

[Last edited by Someone Else at 11-05-2012 07:40 PM]

Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

Spoilers for the prime path problem in a series of secrets.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

File: prime_path.png (10.6 KB)
Downloaded 173 times.
License: Public Domain

Shortest prime path is 25 steps:
NWSWNENWSWNWSWNWSWSENESEN

---

[Last edited by halyavin at 11-18-2012 03:46 PM]

Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

File: halyavins.png (23.2 KB)
Downloaded 132 times.
License: Public Domain

Nice find Halyavin. I took the liberty of making a diagram too, with my script which adds the length labels for easier verification. The path ends at (0,0) according to the script.