Ponder This Challenge - September 2010 - Threaded robot looks for a line

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Since the reels are similar, if the larger reel is 2.54 times bigger in diameter, its thread is 2.542 longer. The question can therefore be rephrased as follows: If you know that your distance from a line L is no more than 1, can you design a path of no more than 6.4516 in length that will guarantee you to intersect the line? The best way to do this is to trace the unit circle - a length of 2 pi = ~6.283 < 6.45. The problem is that we need to get there, which adds the radius (1) and makes the larger reel insufficient.
  But the answer is yes. A possible path is

  1. move, in an arbitrary direction, a distance of 2/sqrt(3), which gets you outside of the circle;
  2. use a tangent to get back to the circle;
  3. travel on the circle for 210 degrees;
  4. leave at a tangent and keep going for 1.

  It is easy to verify that any line tangent to the unit circle must cross our path and that the total length is 2/sqrt(3)+1/sqrt(3)+7*pi/6+1 < 6.4 < 2.542.

  Part B refers to July 2007 ponder this challenge, which asked the same question in a different formulation.

Solvers

• Eli Biham (09/01/2010 07:30 PM EDT)
• Michael Brand (09/01/2010 11:00 PM EDT)
• Chuck Grant (09/02/2010 01:28 AM EDT)
• Joseph DeVincentis (09/02/2010 03:33 PM EDT)
• Adam Daire (09/02/2010 07:16 PM EDT)
• Dan Dima (09/06/2010 01:10 PM EDT)
• Singularity Institute (09/06/2010 05:11 PM EDT)
• Pataki Gergely (09/07/2010 08:22 PM EDT)
• & Keri Kalman (09/07/2010 08:22 PM EDT)
• Jan Fricke (09/08/2010 01:47 PM EDT)
• Piet Orye (09/08/2010 02:03 PM EDT)
• Daniel Bitin (09/09/2010 04:52 PM EDT)
• Mark Mixer (09/10/2010 12:59 PM EDT)
• Florian Fischer (09/10/2010 04:28 PM EDT)
• Gale Greenlee (09/10/2010 10:55 PM EDT)
• John T. Robinson (09/13/2010 10:34 AM EDT)
• Thomas Rohr (09/13/2010 01:00 PM EDT)
• John G Fletcher (09/13/2010 08:11 PM EDT)
• Jonathan Campbell (09/14/2010 07:22 PM EDT)
• Jason Crease (09/14/2010 10:01 PM EDT)
• William Heller (09/15/2010 07:49 AM EDT)
• Arthur Breitman (09/15/2010 02:32 PM EDT)
• Venkata Ramayya Muramalla (09/16/2010 09:51 AM EDT)
• GuangDa HuZhang (09/17/2010 12:58 PM EDT)
• Danny Antonetti & Dan Ignatoff (09/18/2010 03:28 AM EDT)
• Shmuel Menachem Spiegel (09/19/2010 03:03 AM EDT)
• Harald Bögeholz (09/19/2010 12:46 PM EDT)
• Ehud Schreiber (09/21/2010 09:46 AM EDT)
• David Cole (09/23/2010 06:46 PM EDT)
• Gregory J Edwards (09/29/2010 07:35 PM EDT)
• Albert Stadler (09/30/2010 02:44 PM EDT)
• Vishaal Kapoor (09/30/2010 02:49 PM EDT)