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.
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
Challenge:
09/01/2010 @ 11:14 AM EST
Solution:
10/01/2010 @ 11:14 AM EST
List Updated:
09/01/2010 @ 11:14 AM EST
People who answered correctly:
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 & 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)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.