Ariadne’s String

This post is about a problem I learned about at Unsolved K-12, and was reminded of at Integer Sequences K-12. Both conferences were joint meetings of mathematicians and educators, organized by Gord Hamilton. Like several of my favorite problems from those conferences, this problem involved explorations on a lattice.

Here is the problem:
– You must get from the top left corner of an n by n lattice to the bottom left.
– Each step must take you in a straight line to a lattice point.
– Each line segment thus created must be longer than the previous one.
– Your path cannot cross itself.
For example, this is not a successful trip, as the player did not reach the destination:

Taking the last step to the exit would violate the rules, as it would be shorter than the previous step.

On the other hand, this is a successful trip in six steps:

The challenge is to get to the exit after taking the greatest possible number of steps. It turns out for example that for the 5 by 5 lattice, the maximum is nine steps. Can you find that solution?

Of course, you can pose the problem for a lattice of any size. According to Charles R Greathouse IV and Giovanni Resta, the optimal solutions for square lattices with n = 1, 2, …, 9 are: 0, 2, 4, 7, 9, 12, 15, 17, 20. (OEIS A226595) [Correction: Greathouse & Resta were solving a closely related problem: the path could start and end anywhere in the lattice.]

The problem is a nice application of the Pythagorean theorem, and its puzzle-like quality should be engaging. Moreover, students can adjust the level of the challenge by tackling a smaller or larger square. You’ll have to decide whether to reveal the optimal solutions, or whether to just let the class or school record stand.

The figures above were created by Gord Hamilton. When introducing the problem to students, he tells a version of the story about Theseus, the Minotaur, and Ariadne — thus the title of this post. You should make up your own story.


For more about work on lattices and geoboards, go to…
a blog post
Geometry Labs
and follow the links therein.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s