20
$\begingroup$

An ant lives in the origin of the Cartesian Plane. Every morning, at 6 am, it sets out on a 16-hour walk which gets her back home precisely at 10 pm. In the first hour the ant walks exactly one unit, two units in the second hour, three in the third, and so on, until the 16th hour, during which she walks 16 units. During each hour she walks in a straight line, and at the end of every hour´s walk she must find herself at a lattice point and, if not yet home, change directions for the next hour's walk. No where along her walk must her path cross over itself, and her walk on the last hour must be along a different axis then her walk in the first hour. (Her walk, thus, will have the shape of a hexadecagon with sides 1, 2, 3, ..., 16, and all vertices on lattice points.)

If the ant complies with these rules:

  1. What is the furthest away she can get from the x-axis?
  2. What is the furthest away she can get from the origin?

enter image description here

$\endgroup$
14
  • 1
    $\begingroup$ @DmitryKamenetsky A begining: oeis.org/A273089. Also:mathoverflow.net/questions/237374/… $\endgroup$ – Bernardo Recamán Santos Jan 12 at 17:44
  • 2
    $\begingroup$ Is there really any good way to solve for this without just writing code and doing an exhaustive search? $\endgroup$ – Cruncher Jan 12 at 17:46
  • 1
    $\begingroup$ @Cruncher you make it sound like writing a code solution is trivial. I would agree that if someone uses a ready-made tool that would be no more of a challenge than looking up OEIS, but what if the code is hand made...? Although I would like to see a logical solution. $\endgroup$ – Weather Vane Jan 12 at 18:44
  • 1
    $\begingroup$ @WeatherVane Well, surely it's not trivial, but if it's not feasibly solved logically, then it's hardly a puzzle, and more of a programming problem. Programming problems are interesting in and of themselves, it was my first instinct while reading the problem, but it's definitely less pure. $\endgroup$ – Cruncher Jan 12 at 18:48
  • 1
    $\begingroup$ each step, the ant can usually only go up to 4 directions but sometimes it would result in crossing their path. Only on days 5, 10, 13, 15 can the ant move diagonally (Pythagorean triples). Symmetry reduces the possible distinct solutions. There are not that many choices to consider. I think someone could write out all of the possibilities without using a computer. $\endgroup$ – John L Jan 13 at 0:51
12
$\begingroup$

My answer is

The maximum width and the maximum distance come from the same polygon.
$maxcoord = 44$
$distance^2 = 44^2 + 24^2 = 2512$
$distance = 50.12$

The maximum distance from x-axis is the same as the distance from the y-axis.
I have shown the distance from the y-axis (question was edited during making).

enter image description here

The polygon coordinates are
(0 0) (0 1) (2 1) (2 4) (6 4) (10 7) (10 13) (17 13) (17 21) (26 21) (32 13) (32 24) (44 24) (39 12) (25 12) (16 0) (0 0)

Here is the C code, which took about 3 seconds to run

#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXORDER    20      // max 20 in dima[], dimb[]
#define ORDER       16
#define angled      dima
#define CIRCLE      1024    // 'degrees' in a circle
#define CIRCMASK    (CIRCLE-1)
#define QUARTER     (CIRCLE/4)
#define HALF        (QUARTER*2)
#define THREEQ      (QUARTER*3)

typedef struct {
    int dx;
    int dy;
    int ang;
    int dummy;
} turn_t;

int dima[] = { 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 6, 0, 0,  5, 0,  9, 0,  8, 0, 0, 12 }; // smaller
int dimb[] = { 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 8, 0, 0, 12, 0, 12, 0, 15, 0, 0, 16 }; // larger

turn_t turn[MAXORDER+1][16];
int turns[MAXORDER+1];
int histx[MAXORDER+1];
int histy[MAXORDER+1];
int widthres;
int distres;
int distvert;

int cmp(const void *a, const void *b)
{
    return ((turn_t*)a)->ang - ((turn_t*)b)->ang;
}

void buildang(void)
// build table of possible angles and offsets
{
    for(int len=1; len<=ORDER; len++) {
        turn[len][0].dx  = len;
        turn[len][0].dy  = 0;
        turn[len][0].ang = 0;
        
        turn[len][1].dx  = 0;
        turn[len][1].dy  = len;
        turn[len][1].ang = QUARTER;
        
        turn[len][2].dx  = -len;
        turn[len][2].dy  = 0;
        turn[len][2].ang = HALF;
        
        turn[len][3].dx  = 0;
        turn[len][3].dy  = -len;
        turn[len][3].ang = THREEQ;
        
        turns[len] = 4;
        if(angled[len]) {
            turn[len][4].dx  =  dima[len];
            turn[len][4].dy  =  dimb[len];
            turn[len][4].ang = (int)round(atan2(turn[len][4].dy, turn[len][4].dx) * HALF / M_PI);
        
            turn[len][5].dx  = -dima[len];
            turn[len][5].dy  =  dimb[len];
            turn[len][5].ang = (int)round(atan2(turn[len][5].dy, turn[len][5].dx) * HALF / M_PI);
        
            turn[len][6].dx  =  dima[len];
            turn[len][6].dy  = -dimb[len];
            turn[len][6].ang = (int)round(atan2(turn[len][6].dy, turn[len][6].dx) * HALF / M_PI);
        
            turn[len][7].dx  = -dima[len];
            turn[len][7].dy  = -dimb[len];
            turn[len][7].ang = (int)round(atan2(turn[len][7].dy, turn[len][7].dx) * HALF / M_PI);
        
            // flip for the others
            turn[len][8].dx  =  dimb[len];
            turn[len][8].dy  =  dima[len];
            turn[len][8].ang = (int)round(atan2(turn[len][8].dy, turn[len][8].dx) * HALF / M_PI);
        
            turn[len][9].dx  = -dimb[len];
            turn[len][9].dy  =  dima[len];
            turn[len][9].ang = (int)round(atan2(turn[len][9].dy, turn[len][9].dx) * HALF / M_PI);
        
            turn[len][10].dx  =  dimb[len];
            turn[len][10].dy  = -dima[len];
            turn[len][10].ang = (int)round(atan2(turn[len][10].dy, turn[len][10].dx) * HALF / M_PI);
        
            turn[len][11].dx  = -dimb[len];
            turn[len][11].dy  = -dima[len];
            turn[len][11].ang = (int)round(atan2(turn[len][11].dy, turn[len][11].dx) * HALF / M_PI);
        
            turns[len] = 12;
        }
        
        for(int i=0; i<turns[len]; i++) {
            if(turn[len][i].ang < 0)
                turn[len][i].ang += CIRCLE;
        }
        qsort(turn[len], turns[len], sizeof turn[0][0], cmp);
    }
}

void show(int len, int vert)
{
    printf("len=%d:(0 0)", len);
    for(int i=1; i<=ORDER; i++) {
        printf(" (%d %d),", histx[i], histy[i]);
    }
    printf(": v[%d]=(%d %d)\n", vert, histx[vert], histy[vert]);
    fflush(stdout);
}

void recur(int len, int angle)
{
    if(len > ORDER) {
        if(angle != QUARTER && angle != THREEQ && histx[ORDER] == 0 && histy[ORDER] == 0) {
            // polygon is closed, last one is not straight on
            int wvert, dvert, maxd2 = 0, maxx = 0;
            for(int i=1; i<=ORDER; i++) {
                if(maxx < histx[i]) {
                    maxx = histx[i];
                    wvert = i;
                }
                
                int d2 = histx[i] * histx[i] + histy[i] * histy[i];
                if(maxd2 < d2) { 
                    maxd2 = d2;
                    dvert = i;
                }
            }
            
            if(widthres < maxx) {
                widthres = maxx;
                printf("\nwidth=%d wvert=%d\n", widthres, wvert);
                show(maxx, wvert);
#ifdef DRAWING
                makebmp(wvert, "width.bmp");
#endif
            }
            
            if(distres < maxd2) {
                distres = maxd2;
                distvert = dvert;
                printf("\ndist=%d dvert=%d\n", distres, distvert);
                show(maxd2, dvert);
#ifdef DRAWING
                makebmp(dvert, "dist.bmp");
#endif
            }
        }
        return;
    }

    for(int i=0; i<turns[len]; i++) {
        int ang = (turn[len][i].ang - angle) & CIRCMASK;
        if(ang != 0 && ang != HALF) {
            histx[len] = histx[len-1] + turn[len][i].dx;
            histy[len] = histy[len-1] + turn[len][i].dy;
            recur(len + 1, turn[len][i].ang);
        }
    }
}

int main(void)
{
    buildang();
    histx[1] = 0;
    histy[1] = 1;     // vertical
    recur(2, QUARTER); 
    printf("widthres=%d distres=%d dist=%.3f distvert=%d ORDER=%d\n", widthres, distres, sqrt(distres), distvert, ORDER);
    return 0 ;
}

The C code doesn't check for crossings (the maxima didn't have any).

$\endgroup$
2
  • $\begingroup$ Somehow my program failed to find that polygon (and presumably many others, based on Stefan's answer on the linked MO question). Absolutely no idea what have gone wrong though... $\endgroup$ – Bubbler Jan 12 at 23:26
  • $\begingroup$ @Bubbler the one I showed was the only one with that max distance, and I also found your 3 examples with the same maximum coordinate. It was just luck (IMO) that the one I showed has both properties. $\endgroup$ – Weather Vane Jan 13 at 0:39
8
$\begingroup$

Solving this one manually isn't actually that bad. During horizontal and vertical runs they must alternate. So without loss of generality if 1 is vertical, then two is horizontal. The only real choices you get are with the side lengths that are the hypotenuse of a right triangle. Those possibilities are:

short leg long leg hypotonuse
3 4 5
6 8 10
5 12 13
9 12 15

so we can split the segments into groups (1,2,3,4) 5 (6,7,8,9) 10 (11,12) 13 (14) 15 (16)

Within each group they have to alternate horizontal and vertical so if they're all going the same direction (which would maximize distance) then they could be consolidated:

(1,2,3,4) becomes 4 in one direction 6 in the perpendicular direction.

(6,7,8,9) becomes 14 in one direction 16 in the perpendicular direction.

(11,12) is already 11 in one direction and 12 in the perpendicular direction.

To establish a maximum bound we could try to go as far as we can and divide by two (since we have to get back)

this upper bound would be (6 + 4 + 16 + 8 + 12 + 12 + 14 + 12 + 16 ) / 2 = 50

Note that to maximize this 15 had to be diagonal so that 14 and 16 could both be in the same direction.

We can't achieve 50 because that would require us turning around in the middle of our 13 segment, because the lengths for 13 through 16 add to 54. So the solution probably involves turning around between 12 and 13, we just need to find the maximum length that work for both halves. 1 through 12 add to a maximum of 46 so we'll need to be less than that. So let's look at length options for the segments 13-16 (since there's less flexibility on this side)

13 14 15 16 sum
12 14 12 16 54
12 14 9 16 51
5 14 12 16 47
5 14 9 16 44
13 0 12 16 41
... ... ... ... ...

So 44 is the furthest distance that might work, so let's see if we can match that on the other side.

1-4 5 6-9 10 11-12 sum
6 4 16 8 12 46
6 3 16 8 12 45
6 4 16 8 11 45
6 4 14 8 12 44
6 4 16 6 12 44
... ... ... ... ... ...

Looks like we might be able to do it, but we also have to ensure that the perpendicular direction matches so let's check that:

13 14 15 16 sum 13 14 15 16 sum
5 14 9 16 44 12 0 12 0 24
1-4 5 6-9 10 11-12 sum 1-4 5 6-9 10 11-12 sum
6 4 14 8 12 44 4 3 16 6 11 40
6 4 16 6 12 44 6 3 14 8 11 40

If they were all positive it doesn't work, it goes too far, but we can flip the direction of segments that sum to 8 and we might have some solutions.

If we flip 1,3, or 8 we'd end up with a self intersecting path. So, that leaves 5,6, 10, and 11. Where 5 and 6 are too small by themselves and too big together, 11 is too big, and 10 is just right for the second row.

So the final solution is:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
🡹 🡺 🡹 🡺 🡽 🡹 🡺 🡹 🡺 🢆 🡹 🡺 🢇 🡸 🢇 🡸

plot of path

We can easily check that this is the maximum overall distance as well by noting that segments 13-16 can't get further away (without making it unreachable by segments 1-12)

$\endgroup$
1
7
$\begingroup$

The following Python 3 code tries to find all paths that start by moving to (0,1) and return back to origin from (16,0). The vector candidates are hardcoded to eliminate unnecessary branches. (I know they can be reordered to eliminate branches earlier, but I'm too lazy.) It took ~5 minutes to run on my PC.

import time

def cmp(a, b):
  return (a > b) - (a < b) 
def orientation(p, q, r):
  return cmp((q[1] - p[1]) * (r[0] - p[0]), (q[0] - p[0]) * (r[1] - q[1]))

def intersect_test(p, q, r, s):
  return (orientation(p, q, r) != orientation(p, q, s) and
         orientation(r, s, p) != orientation(r, s, q))

vecs = [
  [(16,0)],
  [(12,9),(9,12),(0,15),(-9,12),(-12,9),(-12,-9),(-9,-12),(0,-15),(9,-12),(12,-9)],
  [(14,0),(0,14),(-14,0),(0,-14)],
  [(13,0),(12,5),(5,12),(0,13),(-5,12),(-12,5),(-13,0),(-12,-5),(-5,-12),(0,-13),(5,-12),(12,-5)],
  [(12,0),(0,12),(-12,0),(0,-12)],
  [(11,0),(0,11),(-11,0),(0,-11)],
  [(10,0),(8,6),(6,8),(0,10),(-6,8),(-8,6),(-10,0),(-8,-6),(-6,-8),(0,-10),(6,-8),(8,-6)],
  [(9,0),(0,9),(-9,0),(0,-9)],
  [(8,0),(0,8),(-8,0),(0,-8)],
  [(7,0),(0,7),(-7,0),(0,-7)],
  [(6,0),(0,6),(-6,0),(0,-6)],
  [(4,3),(3,4),(0,5),(-3,4),(-4,3),(-4,-3),(-3,-4),(0,-5),(3,-4),(4,-3)],
  [(4,0),(-4,0)],
  [(0,3),(0,-3)],
  [(2,0),(-2,0)],
  [(0,-1)]
]

solutions = []
def find_polygons(pts, segs, last_vec, vecs):
  if not vecs:
    solutions.append(pts)
    return
  vecs2 = vecs[1:]
  xlast, ylast = last_vec
  for xoff, yoff in vecs[0]:
    if xlast * yoff == xoff * ylast: continue
    newpt = (pts[-1][0] + xoff, pts[-1][1] + yoff)
    newseg = (pts[-1], newpt)
    if (not vecs2) and newpt != (0,0): continue
    exclude_first = not vecs2
    if any(intersect_test(*seg,*newseg) for seg in segs[exclude_first:-1]): continue
    find_polygons(pts + [newpt], segs + [newseg], (xoff,yoff), vecs2)

start = time.time()
find_polygons([(0,0)], [], (99,1), vecs)
print(len(solutions))
end = time.time()
print(end - start)

maxdist = max(max(max(abs(x),abs(y)) for x,y in pts) for pts in solutions)
print([pts[:0:-1] for pts in solutions if any(maxdist in pt or -maxdist in pt for pt in pts)])

maxdist2 = max(max(x*x+y*y for x,y in pts) for pts in solutions)
print([pts[:0:-1] for pts in solutions if any(x*x+y*y==maxdist2 for x,y in pts)])

In total, the program found

681 distinct paths modulo reflection and rotation.

According to the program, the answer to Q1 is

there are three paths that achieve distance of 44 from y-axis (which can be reflected by the line y=x to get the same distance from x-axis), which are:

[(0, 0), (0, 1), (2, 1), (2, 4), (6, 4), (9, 8), (9, 14), (16, 14), (16, 6), (25, 6), (33, 12), (44, 12), (44, 0), (39, -12), (25, -12), (16, 0)]
[(0, 0), (0, 1), (2, 1), (2, 4), (6, 4), (10, 1), (16, 1), (16, 8), (24, 8), (24, 17), (32, 11), (32, 0), (44, 0), (39, -12), (25, -12), (16, 0)]
[(0, 0), (0, 1), (2, 1), (2, 4), (6, 4), (10, 7), (16, 7), (16, 14), (24, 14), (24, 5), (32, 11), (32, 0), (44, 0), (39, -12), (25, -12), (16, 0)]

and the answer to Q2 is

there is only one path that achieves squared distance 372+332=2458 (sqrt(2458) ~ 49.578) from the origin, which is:

[(0, 0), (0, 1), (2, 1), (2, 4), (6, 4), (6, 9), (12, 9), (12, 16), (20, 16), (20, 25), (26, 33), (37, 33), (37, 21), (42, 9), (28, 9), (16, 0)]

$\endgroup$
2
  • $\begingroup$ your intersection algorithm has a bug. Orientation should be return cmp((q[1] - p[1]) * (r[0] - p[0]) , (q[0] - p[0]) * (r[1] - p[1])) note the last point is p not q. $\endgroup$ – Rick Jan 13 at 16:12
  • 1
    $\begingroup$ re-running your code with the correction reveals 882 distinct paths, with one additional path of x distance 44 which is also the longest squared distance. $\endgroup$ – Rick Jan 13 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.