6
$\begingroup$

An ant resides at the origin of the Cartesian plane. One morning she sets out on a long excursion of its first quadrant and pledges to walk a different prime number of units every day starting with 2, always in a straight line, always within the same quadrant, and always staying overnight at lattice points. Each day, the number of units she walks is the prime number immediately following the prime number of the previous day (though in a different direction so as not to walk in a straight line on two consecutive days). At the end of her excursion, she returns home never having crossed or retraced her own path.

(Her walk will thus be a polygon of sides -in order- 2, 3, 5, 7, ..., with one of its vertices in the origin and all the others in lattice points in the first quadrant.)

a) Strictly following these rules, what is the earliest the ant can be back at the origin?

b) Can she make such excursions of any number of days greater than that minimum?

An earlier related puzzle: An ant's walk in the Cartesian Plane

Also: https://mathoverflow.net/questions/237374/lattice-n-gons-with-ordered-side-lengths-1-2-3-n

Improve this question
$\endgroup$
8
  • $\begingroup$ Must the points she walks to have integer coordinates? Must she walk in orthorgonal directions (ie. always N, S, E or W)? $\endgroup$
    – Weather Vane
    Commented Nov 15, 2023 at 20:05
  • 1
    $\begingroup$ Wheather Vane: Yes, and no. But at the end of day's walk, she must be at a lattice point. $\endgroup$
    – Bernardo Recamán Santos
    Commented Nov 15, 2023 at 20:08
  • 1
    $\begingroup$ @Bass: I'm sorry, but that's not how it's supposed to work. You're supposed to wait to answer until a question is clear. If there are pending questions in the comments and you still decide to answer, it's on you. $\endgroup$
    – Matthieu M.
    Commented Nov 16, 2023 at 14:37
  • 1
    $\begingroup$ In this case, isn't the close vote now too late? Since the question is now clear (at 2023-11-16 01:38:55Z). Granted, I wasn't available when the original version of the question was up, but I can empathize with you feeling bad that an answer you've crafted is no longer valid. But I'd say, what's done is done, seems like the question is in its final version now. $\endgroup$
    – justhalf
    Commented Nov 16, 2023 at 15:29
  • 1
    $\begingroup$ @Bass: The question still not being clear (touching without crossing) is definitely a reason to close-vote... You didn't mention that in any comment, though, so the OP cannot know it needs to be clarified, and we cannot know it should be closed :x $\endgroup$
    – Matthieu M.
    Commented Nov 16, 2023 at 16:30

4 Answers 4

Reset to default
8
$\begingroup$

Answer (b)

There are more solutions.

The first three are
7 days: (0,0) (2,0) (2,3) (6,6) (13,6) (13,17) (0,17) (0,0)
11 days: (0,0) (2,0) (2,3) (6,6) (13,6) (13,17) (1,12) (1,29) (20,29) (20,52) (0,31) (0,0)
13 days: (0,0) (2,0) (2,3) (7,3) (7,10) (18,10) (30,15) (22,0) (41,0) (41,23) (21,44) (21,75) (9,40) (0,0)

enter image description here

The Pythorean primes with which we can go diagonally and stay on the lattice can be verified from OEIS:
5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197, 229, 233, 241, 257, 269, 277, 281, 293, 313, 317, 337, 349, 353, 373, 389, 397, 401, 409, 421, 433, 449, 457, 461, 509, 521, 541, 557, 569, 577, 593, 601, 613, 617 . . .

Edit: I was beginning to think that there are only prime solutions, but

the next two solutions are
15 days: (0,0) (2,0) (2,3) (7,3) (7,10) (18,10) (6,15) (21,23) (21,42) (44,42) (64,21) (95,21) (83,56) (43,47) (0,47) (0,0)

17 days: (0,0) (2,0) (2,3) (7,3) (7,10) (18,10) (18,23) (35,23) (35,42) (58,42) (78,21) (78,52) (115,52) (75,61) (75,104) (28,104) (0,59) (0,0)

enter image description here

enter image description here

Improve this answer
$\endgroup$
11
  • $\begingroup$ This looks cool. What's your method of solving? $\endgroup$
    – justhalf
    Commented Nov 16, 2023 at 14:29
  • $\begingroup$ Really beautiful! $\endgroup$
    – Bernardo Recamán Santos
    Commented Nov 16, 2023 at 14:31
  • $\begingroup$ @justhalf solved with BFS, discarding anything that goes out of the quadrant, or crosses a previous line. $\endgroup$
    – Weather Vane
    Commented Nov 16, 2023 at 14:37
  • 1
    $\begingroup$ @BernardoRecamánSantos re part (b) – the number of solutions grows rapidly: 7 days 1, 11 days 2, 13 days 16, 15 days 66, 17 days 525, 19 days 5098... With no touching any part of the path, except finishing at (0,0). $\endgroup$
    – Weather Vane
    Commented Nov 17, 2023 at 14:59
  • 1
    $\begingroup$ @WeatherVane: These numbers certainly deserve being in the OEIS as already are their close cousins:oeis.org/A273089. Nice job! $\endgroup$
    – Bernardo Recamán Santos
    Commented Nov 18, 2023 at 14:21
10
$\begingroup$

The ant can get home in 7 days (although my ant is walking clockwise):
Day 1: 2 N (0,2)
Day 2: 3 E (3,2)
Day 3: 5 NE (6,6)
Day 4: 7 N (6,13)
Day 5: 11 E (17,13)
Day 6: 13 S (17,0)
Day 7: 17 W (0,0)

I believe this is the minimum, but don't currently have a proof. Don't know whether they can do it again.

Improve this answer
$\endgroup$
8
$\begingroup$

Here's a (messy) picture proof of optimality for @melmackian's solution:

enter image description here

Legend:

  • Red lines: first 3 moves (2,3,5 units)
  • Small black circles with coordinates: some lattice points at a too small prime distance from origin
  • Green circles: possible positions after the fourth move (7 units)
  • Blue circles with coordinates: lattice points at distance 13 from home
  • Yellow circles with coordinates: lattice points at distance 17 from home

The 5th move cannot reach a blue circle from a green circle: a move of 11 units must be orthogonal, so it's enough to check green-blue pairs on the same line, and none of those are exactly 11 units apart.

The 6th move can reach a yellow circle with moves 11 and 13 units long: for example like this:

enter image description here

(@melmackian's solution is actually a reflection of this one, and there's also another path that produces a polygon with a zero degree angle between the shortest and the longest side; I chose this one to rescue at least the tiny bit of aesthetics I could, while complying with OP's wish of going anticlockwise.)

As for question b, the answer is

Yes. For example: enter image description here

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Interesting, but in (b) the OP says in comment "path must not be crossed over or retraced". $\endgroup$
    – Weather Vane
    Commented Nov 16, 2023 at 0:21
  • 1
    $\begingroup$ Comments are not part of the question though. $\endgroup$
    – Bass
    Commented Nov 16, 2023 at 1:01
  • $\begingroup$ @Bass it is now $\endgroup$
    – justhalf
    Commented Nov 16, 2023 at 2:56
  • $\begingroup$ Perhaps I'm misinterpreting your response to (b), but it seems not to satisfy the rule "At the end of her excursion, she returns home never having crossed or retraced her own path." Though I guess that was added as a clarification after this answer was posted. $\endgroup$
    – John Bollinger
    Commented Nov 16, 2023 at 17:55
2
$\begingroup$

The ant can return home in

4 days. The idea is to make a 3-4-5 right triangle, using the difference of 7 and 11 to make the final 4 side:

enter image description here

I'm not sure if points on the axes count as "in the first quadrant", but I think it's reasonable to permit them, as we require the origin to be the start/end point of this first quadrant tour.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ doesn't the ant have to start with a walk of length 2? $\endgroup$
    – juicifer
    Commented Nov 15, 2023 at 20:46
  • 1
    $\begingroup$ @juicifer Shoot, the problem has changed a bit. At first, the ant neither needed to stop on lattice points, nor start with a side length of 2. $\endgroup$
    – Nuclear Hoagie
    Commented Nov 15, 2023 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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