PUZZLE IBM-149
Threaded robot looks for a line
IBM Research · Ponder This · 2010-09
IBM Ponder This #149 · September 2010
Part A
A tiny robot carrying a thread rolled on a 1 cm diameter reel started walking from somewhere on an infinitely long line L and arrived at point x.
Alas, the thread left by the robot on its way has disappeared. Now the woeful robot wants to get back to somewhere on the line L, but it does not remember anything, and would not even recognize the line L unless it actually stepped on it.
The robot has another reel of the same kind of thread, but longer: a reel 1 inch in diameter. Can you help the robot design a path that would ensure that by using the longer thread in the same way (i.e., continuously leaving the thread as a trace of its path), it can guarantee that it will get back to the line L before the thread runs out?
If you can, show how. If not, prove that no path can guarantee success.
Update: September 7th: the robot got to the point x exactly when it run out of thread and then the thread disappeard.
The two reels have the same spindle and the same kind of thread spiraling around it. The bigger, 1 inch reel has more rounds.
Part B (bonus question)
We already asked a similar question, which we can formulate as follows: Given that the unknown line L intersects a 1x1 square, can the robot use a 2.64 long thread and guarantee to intersect the line L?
In this part, unlike part A, the robot can cut the thread; move without using thread; start leaving thread again later; and repeat it again and again.
Our (bonus) question is this: When did we previously ask this question?
Update: September 7th: the robot has to leave the thread in order to detect crossing the line L.
Solution
Best opened after a real attemptTo be added.