Ant in the Desert

This problem came out of a brainstorming session for ideas for reasonably short, self-contained programming problems:

An ant is walking in a straight line across the desert, leaving a periodic (i.e., repeating) pattern of equally spaced 1s and 0s (or ant-droppings and not-droppings, if you like) behind it as it moves.  You are a myrmecologist-mathematician also walking in the desert, and you come upon the ant’s trail.  The ant is long gone.  However, depending on the pattern of its trail, which you know, you may be able to determine which direction the ant was moving.

What is the shortest possible repeating pattern left by the ant that would allow you to unambiguously determine its direction?

 

2 thoughts on “Ant in the Desert

  1. I’m pretty sure the minimum length repeating pattern of equally spaced 1s and 0s that is directionally asymmetric has length 5. There are two of them, “…110101101011010…” and “…1001010010100101…” and their directionally reversed mirror images.

    • Your description of the required properties of the trail is correct, but note that the two examples that you give are not directionally asymmetric. In the first example, read left to right as “…110101101011…”, if you instead read from right to left, but starting with a rightmost 1 in a consecutive pair of 1s, then it also reads “…110101101011…”.

      We can make the problem more precise by representing a trail with period n as a function f:{0,1,2,…,n-1}->{0,1}, so that, for example, one representation of the above trail is f(0)=1, f(1)=1, f(2)=0, f(3)=1, f(4)=0. The directional asymmetry property means that there does *not* exist an integer k such that f(j mod n)=f((k-j) mod n) for all j. In this example, there *is* such a k, namely k=1. (Intuitively, this requirement says that we must not be able to first reverse (-j) and then cyclically shift (+k) the pattern and leave it unchanged.)

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s