A Bug Strife

Young Cleo has lost her ant. The ant, whose name is Tony, didn’t have any particular complaints about life under Cleo’s care; he just decided he wanted to explore the sights and scents of the world for himself, rather than reading about them on Crickipedia*. He had written Cleo a fond pheromonal farewell on the side of his tank, so he assumed she was ok with this.

The escape was a particularly manic and haphazard affair. Cleo had been taking Tony for his daily walk down the long, straight path outside their house. She had let Tony off his leash because he was so good at walking to heel. Suddenly a huge gust of wind came blasting down the length of the path and Tony, seeing his chance for High Adventure, chose not to cling to the pavement and went careening into the distance. Bizarrely, the wind abruptly changed and came rushing back in the exact opposite direction. Cleo has no idea where on the path Tony landed, ahead of her or behind.

Cleo is naturally concerned, especially since the local insect-delicatessen (‘Insectivoracious’) is just down the road. She’s determined to find Tony, but he’s pretty small. Due to her young age, Cleo has never ventured all that far from her house, and she has no idea how far the road spans in either direction since every house is labelled with an un-orderable symbol rather than a number (a particularly valiant attempt at egalitarianism on the part of the local council) - Cleo lives at ‘Purple Blob’**. As an aspiring cosmologist, she conjectures that the road has infinite length and that Tony might be anywhere along it, moving in one direction or the other at a fixed speed (which could include zero – just staying put).

Cleo can’t see Tony without getting to the ground and examining closely, so she has to check for him one spot at a time. Conveniently, the pavement is split into fairly long, thin slabs, spanning its entire width, and she thinks she can check one of them thoroughly in about a minute. Tony is very safety-conscious and will almost certainly stick to the path. Moreover, Cleo has noticed that left to his own devices, Tony moves an exact number of slabs per minute, but she can’t for the life of her remember how many. She considers her own speed not to be an issue, since she can get her mum, who will no doubt be horrified at Tony’s impromptu departure, to drive her up and down the road at a speed that makes Tony’s negligible.

Cleo starts off where she is, first checking the slab she's standing on, then moving one step forward and checking that slab.

After a few minutes, she realises this might never work. What if Tony is behind her and moving away? Then she’s fruitlessly checking a set of slabs that he’ll never appear in. She tries a different approach, jumping back to the first unchecked slab behind her, then forward to the first unchecked slab in front of her, then back again, and so on.

This still won’t work, she realises. If he’s moving away from her (and there’s a roughly 50% chance he is) in either direction, he’ll be moving away faster than she can check, since on average she checks only half a slab in each direction every minute. But if she skips some, she could end up missing him! This is going to take some thought.

Can Cleo develop a search strategy that will certainly result in her finding Tony eventually after a finite time, so long as she never gives up until she’s successful?

Answer here! Skip the next block if you don’t want a…

HINT:
If we did know Tony’s initial position and velocity, how could we express his position after time t (measured in minutes)? This is where Cleo has to check at that time, except that she doesn’t know the initial conditions. How can she cycle through the possibilities in a way that eventually checks each one?

I first encountered this problem in a mathematically identical, but narratively distinct, form: a train starts at an unknown integer along a track described by a number line of infinite length in both positive and negative directions. There are sensors at the integer values along this line that can tell you whether or not the train is there, but only at the time you check them. The velocity of the train is known only to be an integer, positive or negative, and at every time-step you can check exactly one sensor. Arguably some extra suspension of disbelief is required for my version, since Cleo’s equivalent to ‘checking the sensor’ is actually driving to the spot that needs examining: Cleo moves at unlimited speed! On the other hand, our assumptions of an ‘infinite road’ and ‘unlimited speed’ aren’t really any crazier than an infinitely long train track with an infinite number of sensors along it, and the signal from each sensor must take some time to reach us, too. Perhaps the biggest assumption here is that Tony, being a male ant, is still alive after any appreciable length of time! It sucks to be a boy in the insect world.

---

*The insectese translation of Wikipedia is in the cricket dialect, a decision made by its grasshopper founders and the source of no small amount of contention in the insect world.

** You might complain that hues and shapes do still admit an ordering, and you'd be right! If this troubles you, feel free to substitute your favourite unorderable set.