Hello, here is an puzzle I thought of recently that I've only half-solved. Background: Suppose there is a suburb with houses occupying/centered on each integer pair of points (x,y) on an infinite plane. Each house has a teleporter at its center configured to teleport to any house an integer distance away. Naturally when people wanted to get from say (0,0) to (a,b) they went horizontally or vertically relative to the grid, going from (0,0) to (a,0) to (a,b). However, perhaps from overuse, the option of moving horizontally or vertically relative to the grid was lost.

In this scenario, is it possible to get from a point to any other in a reasonable amount of teleports (that is, is there an upper bound on teleports needed?) . If so, what is the most teleports it could possibly take?

My half-solution :

Spoiler:

Just navigating using a (3,4,5) triangle and scaled up versions of it (3x,4x,5x), you can get near your desired x coordinated by going from (0,0) to (4x,3x) to (0, 6x), getting to the nearest multiple of 6 near the x coordinate, jumping around from there on the (3,4,5) triangle can get exactly the correct x coordinate, repeat for y coordinate, and the worst case scenario of this is an upper bound.

Feel free to come up with variations of this where the teleporter breaks down in other ways if you're interested.

Clearly we are dealing with Pythagorean triples. Consider these three: {3,4,5}, {5,12,13}, {8,15,17} Jumping along each hypotenuse is equivalent to jumping along both legs in x and y direction. Each leg can be positive or negative and can correspond to x or y.

12 + 4 - 15 = 1 5 + 3 - 8 = 0 The above corresponds to the x and y coordinates of moving {3,4,5}, {5,12,13} in positive direction and {8,15,17} in negative direction. The actual moves would be a 5 and 12 hop and a 17 hop in "other" direction. The end result is a net 1 unit displacement from starting position. Since x and y are interchangeable (by simply rotating the Pythagorean triple triangles over 90, 180, 270 degrees), you can access any house within 1 unit of your starting position in 3 hops.

It is then trivial to show the bound is merely 3 times the bound of the "traditional" method.

My modification: What if all the houses that lie on (x,y) such that x+y = prime is removed?

This is a block of text that can be added to posts you make. There is a 300 character limit.

The following three hops will get you to (a,b). All of these are integer multiples of some rotation/reflection of (3,4), and thus have integer distance.

I don't think it's possible to move to (0,1) in two hops, so that would make the solution 3.

I propose a different restriction: Rather than disallowing horizontal and vertical teleports, disallow any teleports which pass directly through another teleporter. That is, the x and y distances of each teleport must be relatively prime.

Nice solutions. Here is a proof that you can't get from (0,0) to (1,0) in two teleports :

Spoiler:

If it were possible, then there would exist a point (x,y) (which can be assumed to have x and y greater than 1) such that it is an integer distance from both (0,0) and (1,0). Because of this, x^2 + y^2 is square, and so is (x-1)^2 + y^2. It can be seen that sqrt(x^2+y^2) > sqrt((x-1)^2 + y^2), but note also that sqrt(x^2+y^2) < sqrt((x-1)^2 + y^2) + 1, as the second term there is the length form (x,y) to (0,1) and then from (0,1) to (0,0) , which is not a straight line so is greater than the straight distance sqrt((x-1)^2+y^2). This leads to a contradiction, as writing both those inequalities shows sqrt(x^2+y^2) , supposedly an integer, squeezed between two consecutive integers. Therefore our original assumption it was possible to get from (0,0) to (0,1) with two teleports is wrong.

Perhaps there is a nicer proof of that fact, though maybe not. Both the proposed variations of the problem seem interesting, though I prefer the second as it could better fit with the background, it seems reasonable to have teleports unable to go through other teleporters.

Nitrodon wrote:...the x and y distances of each teleport must be relatively prime.

Spoiler:

Two hops are always enough. This is because you can make any teleport where either the x or y distance is 1. So to get from (0,0) to (a,b), make a stop at (1,b-1).

Here's a restriction: on any given journey, all teleports must have the same distance. Unfortunately, one particular distance is not allowed: the distance from you to your goal. Can you get to any location in a reasonable number of hops? EDIT: Both parts of this post assumed that the integer distance restriction only applied to the original problem. If Nitrodon's relatively prime version also has the integer distance requirement, then my solution doesn't work.

Last edited by Lopsidation on Sun Dec 28, 2014 11:50 pm UTC, edited 1 time in total.

Lopsidation, I think Nitrodon's variation, besides requiring the x and y distances to be relatively prime, continued with the restriction to integer distance jumps, so your solution would not work.

Clearly there are a lot of variations on this problem, which is cool. Variations could also be made involving an infinite three (or more) dimensional "apartment complex".

Nitrodon wrote:I propose a different restriction: Rather than disallowing horizontal and vertical teleports, disallow any teleports which pass directly through another teleporter. That is, the x and y distances of each teleport must be relatively prime.

Correct me if I'm wrong, but doesn't my solution already satisfy this condition?

Lopsidation wrote:Here's a restriction: on any given journey, all teleports must have the same distance. Unfortunately, one particular distance is not allowed: the distance from you to your goal. Can you get to any location in a reasonable number of hops?

Doesn't Nitrodon's solution satisfy this condition?

This is a block of text that can be added to posts you make. There is a 300 character limit.

Cradarc, your first solution takes linear time to get from point A to point B. I think both Nitrodon and I want a better travel time. If possible, a constant number of hops. And it doesn't look to me like Nitrodon's original three-hop solution uses all teleports of equal length.

I didn't realize Nitrodon's alternate restriction used the integer distance requirement as well. For reference, my equal-length teleports restriction does not include that restriction. Hmm, I wonder what happens if you require equal-length integer distance teleports.

Lopsidation wrote:Cradarc, your first solution takes linear time to get from point A to point B. I think both Nitrodon and I want a better travel time. If possible, a constant number of hops.

That changes everything. Do we even know if a constant hop solution exists for the original problem? Remember every integer coordinate has to be reached. As x,y get large, there are fewer and fewer Pythagorean triples of comparable magnitude. http://upload.wikimedia.org/wikipedia/commons/9/97/Pythagorean_triple_scatterplot2.png You will have to use smaller hops to "focus" onto the exact coordinate. I think it's highly unlikely a constant hop solution exists.

Lopsidation wrote:And it doesn't look to me like Nitrodon's original three-hop solution uses all teleports of equal length.

Well he said:

Nitrodon wrote:All of these are integer multiples of some rotation/reflection of (3,4)

(3,4) corresponds to a length of 5. So every hop is length 5. It's just that he took multiple hops in the same "direction", and you never specified each hop had to be in different directions.

This is a block of text that can be added to posts you make. There is a 300 character limit.

Cradarc wrote:...(3,4) corresponds to a length of 5. So every hop is length 5. It's just that he took multiple hops in the same "direction", and you never specified each hop had to be in different directions.

You don't need to use multiple hops of distance 5 on (3,4) ; you could rather do it all in one jump. For instance, on (6,8) you could move 10 in one hop, 15 on (9,12) ect. So Nitrodon's solution does only use three hops to get to any point under the initial rules, but they are hops of different lengths.

Heptadecagon wrote:You don't need to use multiple hops of distance 5 on (3,4) ; you could rather do it all in one jump. For instance, on (6,8) you could move 10 in one hop, 15 on (9,12) ect. So Nitrodon's solution does only use three hops to get to any point under the initial rules, but they are hops of different lengths.

I think you missed my point. Yes, he can reduce the number of hops to 3 by combining multiple hops in the same direction. What I'm saying is, he can also "uncombine" them to satisfy Lopsidation's requirement.

This is a block of text that can be added to posts you make. There is a 300 character limit.

Nitrodon wrote:disallow any teleports which pass directly through another teleporter

I've got a solution for Nitrodon's variant in <=10 hops, but I think we can do better...

Spoiler:

Cradarc wrote:12 + 4 - 15 = 1 5 + 3 - 8 = 0

So Cradarc gives us a method where three hops will shift us an arbitrary 1-distance. This is useful.

Heptadecagon (sort of) wrote:For any valid hop (a,b) we have a two hop (a,b), (a,-b) which takes us to (2a,0).

This is also useful.

Let's look at a class of Pythagorean Triples. We can find all odd m in triples of the form m,n,n+1 (or being more precise, for all x we have the triple 2x+1, 2x(x+1),2x(2x+1)+1 -- with 2x+1 and 2x(x+1) coprime). Using our two-hop trick, this lets us hit any 2 mod 4 coordinate in two hops. Using Cradarc's trick from there we can hit odd coordinates in 3 more hops (5 total). 0 mod 4 can be done as 2 mod 4 twice, for four hops total. This gives us a solution to Nitrodon's variant at 10 hops (5 each, doing the two coordinates independently)

While writing this I seem to have improved on my solution, but I think the process is informative, so I'm just going to do this as two separate posts.

Again, Nitrodon's Primitive Pythagorean Teleporter variant, <= 6 hops to arbitrary (a,b). I suspect (hope!) we can improve on this, but I haven't so far been able to.

Spoiler:

For this solution we'll just be hopping along Pythagorean triples of the form m,n,n+1 (2x+1, 2x(x+1), 2x(2x+1)+1) which exist for all m odd (all x). Observe: m,n co-prime; n = 0 mod 4.

Are a,b both odd? We'll pick two hops m1=a+2, m2=b+n1. We now have (n2+2, 0) remaining. n2 = 0 mod 4, so this can be done with two more hops m3=(n2+2)/2. Are either a or b even? Well it will take at most two hops to make a,b both odd.

New (awful) variant: Can we visit every house exactly once?

Lopsidation's equal-distance hop problem can't always be done in two jumps: any solution in two jumps from (0,0) to (x,y) would have to land on a line going through (x/2,y/2) perpendicular to the line from (0,0) to (x,y), and that leads to a linear Diophantine equation that doesn't always have solutions.

Also, it might be of use somewhere here, a square may be the sum of two squares in more than one way: 5^4 = 25^2 = 7^2 + 24^2 = 15^2 + 20^2 ; 5^6 = 125^2 = 35^2 + 120^2 = 75^2 + 100^2. Interesting that the smallest examples I found (via program) are powers of 5... The first square the sum of two squares in 4 ways is 4225 = 5^2 * 13^2, which still has 5 in its factorization... hmm... though very likely this is becoming unrelated

I feel it should be possible to get everywhere, maybe even on just a (3,4,5) triple!

@Cradarc: The point is to get to any location in a reasonable number of hops. If I can't visit my friend at (2158096541, 1805984859403) in less than a million hops, then what's the point of having teleporters?

Also, solved ekim's "every house exactly once" problem.

Spoiler:

It is possible.

First, I give an algorithm for going from any house A to any other house B, without visiting any other house in a given forbidden finite set S. To do this, first make a HUGE jump from A to another house A'. Then, working backwards from house B, jump a HUGE distance away in the same general direction to reach house B'. How huge is huge? So huge that, if you zoom way out, A' and B' are practically neighbors while S is a speck on the horizon. Now, use Nitrodon's solution to go from A' to B' in at most three hops. Since both A' and B' are very very far away from S, and comparatively close to each other, this method will never get anywhere close to S. So, modulo working out annoying details, this algorithm works.

Now, we will use this algorithm to visit every house once. First make a list of all houses. Then, repeatedly use this algorithm to visit the next unvisited house on the list, forbidding any house that has already been visited. This procedure visits every house exactly once.

Got Nitrodon's variant in three hops for odd,even destination, four hops for odd,odd and for even,even - and by looking at primitive triples mod 4 (the legs are always (1 or 3,0)) you can see that (2,2) can't be done in fewer than 4. (Not sure about odd,odd. Conceivable that we could do this in two.)

Spoiler:

My proof is a kind of ugly case-by-case thing. The main trick is using these m,n,n+1 triangles to get rid of anything with a 2 mod 4, and m,n,n+2 triples (primitive for all m = 0 mod 4) to get rid of the 0 mod 4 cases.

For the original problem statement we have Heptadecagon's nice proof that (0,1) isn't reachable in fewer than three hops, but are there infinitely many houses like this? Or can we reach almost all houses in 2 hops?

Nice solution of getting to every house exactly once! While that shows you can get to any house when a finite amount of houses are removed, can removing a finite amount of houses increase the potentially needed teleports arbitrarily high? Or is there an upper bound on teleports for that as well?

Also, I proved that for any integer two hop from (0,0) to (1,1), the first hop cannot go to the first of third quadrant of the plane, though that isn't helpful.

(1,1) can be done with (-20,21) (21,-20) (0,2) can't be done in 2 hops

Spoiler:

the two hops will look like (a,-b), (-a,b+2) a^2+b^2=c^2; a^2+(b+2)^2=(c+k)^2 k>2 means c<b, and k=2 gives c=b, so k=1 but (b+2)^2-b^2 = 4b+4 is even, and (c+1)^2-c^2=2c+1 is odd

I was hoping to show that infinitely many 0,k couldn't be done in 2, but for all I know all 0,k; k>2 can be done in 2 hops. Working on that.

(0,k) can be reached in two hops for all k>2. The solution, though encouraging, isn't terribly enlightening.

I've still no idea about the rest of our lattice.

Spoiler:

For k odd use the m,n,n+1 triples: (2k-1,2k(k-1),2k(k-1)+1) and (2k+1,2k(k+1),2k(k+1)+1) but scale them by (k+1)/2 and (k-1)/2 respectively The larger legs of these scaled triples will both be k(k-1)(k+1), and the smaller legs will differ by k For even 2^n*k just take the solution for k and scale by 2^n And for powers of two 2^(n+2), use any solution to (0,4) (such as (-5,12) (9,-12)) scaled by 2^n

Heptadecagon wrote:Nice solutions. Here is a proof that you can't get from (0,0) to (1,0) in two teleports :

Spoiler:

If it were possible, then there would exist a point (x,y) (which can be assumed to have x and y greater than 1) such that it is an integer distance from both (0,0) and (1,0). Because of this, x^2 + y^2 is square, and so is (x-1)^2 + y^2. It can be seen that sqrt(x^2+y^2) > sqrt((x-1)^2 + y^2), but note also that sqrt(x^2+y^2) < sqrt((x-1)^2 + y^2) + 1, as the second term there is the length form (x,y) to (0,1) and then from (0,1) to (0,0) , which is not a straight line so is greater than the straight distance sqrt((x-1)^2+y^2). This leads to a contradiction, as writing both those inequalities shows sqrt(x^2+y^2) , supposedly an integer, squeezed between two consecutive integers. Therefore our original assumption it was possible to get from (0,0) to (0,1) with two teleports is wrong.

Perhaps there is a nicer proof of that fact, though maybe not. Both the proposed variations of the problem seem interesting, though I prefer the second as it could better fit with the background, it seems reasonable to have teleports unable to go through other teleporters.

As to the 0,1 situation, if we have point [X,Z] and observe that side OX (O is point [0,0]) is an integer, then side OZ is of length OX+1cos(q) or OX+1sin(q) [q is the angle between sides OX and O[0,1](the respective length of our 'third' side after we choose any arbitrary integer-point on our lattice) is going to be between OZ and OZ+1, as 1cos(q) and 1sin(q) must be either 0, 1, or a non-integer value between 0 and 1, all of which break our system for either yielding three points that aren't a triangle (a line) a right triangle (can't move vertically or horizontally in our lattice to point OX) or a non-integer length for side OZ.

This might be made cleaner, but our 1cos(q) and 1sin(q) non-integer lengths pretty much seal our third side length as not being an integer, doesn't it?

Imagine your first move is the short one (they can't be equal length because they'd be on a half integer), and uses the triple (a, b, c) with a^2+b^2 = c^2. Your second move must have length squared (a+1)^2 +b^2 (wlog). But, c>a, so 2c +1 > 2a +1, so c^2 < (a+1)^2 +b^2 < (c+1)^2 and this cannot be a square.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit wrote:Perhaps the easiest proof that its impossible.

Spoiler:

Imagine your first move is the short one (they can't be equal length because they'd be on a half integer), and uses the triple (a, b, c) with a^2+b^2 = c^2. Your second move must have length squared (a+1)^2 +b^2 (wlog). But, c>a, so 2c +1 > 2a +1, so c^2 < (a+1)^2 +b^2 < (c+1)^2 and this cannot be a square.

I think the following is easier.

Spoiler:

The two moves are two sides of a triangle, the third side being of length 1. By the triangle inequality, those two sides cannot differ by more than 1. Therefore if one of the moves has integer length, the other cannot.

The two moves are two sides of a triangle, the third side being of length 1. By the triangle inequality, those two sides cannot differ by more than 1. Therefore if one of the moves has integer length, the other cannot.

Very nice, all the numbers I wrote out were really unnecessary, this gets to the heart of the matter.

While earlier it was reasoned (not quite proved here) that you can still make it to any house if a finite amount of houses are removed, but what if a finite amount of houses are removed from every row (so potentially an infinite # removed in total) ?

I can keep you stuck at the origin, but it will involve disabling quite a few teleporters.

Spoiler:

As n^2 gets big, the difference between consecutive squares (n+1)^2-n^2 also gets big. So for a given leg length, there's an upper bound on the length of the other leg if we're going to have an integer length hypotenuse: it can't be so big that the square of our short leg won't even carry us to the next square. (n+1)^2-n^2=2n+1 For the nth row, get rid of (n^2-1)/2 teleporters to either side of the y axis. The only integer length hops remaining will be along the axes themselves.

ekim wrote:(0,k) can be reached in two hops for all k>2. The solution, though encouraging, isn't terribly enlightening.

I've still no idea about the rest of our lattice.

Spoiler:

For k odd use the m,n,n+1 triples: (2k-1,2k(k-1),2k(k-1)+1) and (2k+1,2k(k+1),2k(k+1)+1) but scale them by (k+1)/2 and (k-1)/2 respectively The larger legs of these scaled triples will both be k(k-1)(k+1), and the smaller legs will differ by k For even 2^n*k just take the solution for k and scale by 2^n And for powers of two 2^(n+2), use any solution to (0,4) (such as (-5,12) (9,-12)) scaled by 2^n

Doesn't that trivially set a constant upper bound for the rest of the lattice?

Spoiler:

To get to (a,b), with a>2 and b>2, first use your method to get to (0,b), then set your new location as the origin, rotate your frame of reference 90 degrees, and use your method to get (0,a). So 4 hops maximum for everything outside the (2,2) box.

You're right, that gives us <=4 for (almost) everything else, but Nitrodon already gave us 3 everywhere and I was hoping to show 2 almost everywhere (though as you can see it's looking pretty ugly)

TBH I was hoping to show the opposite, to just find infinitely many that needed at least 3 hops, but that's looking less and less likely