I just came up with this problem yesterday.
Problem:
Assume there is an important segment of straight line AB
that needs to be watched at all time. A watchdog can see in one direction in front of itself and must walk at a constant non-zero speed at all time. (All watchdogs don't need to have the same speed.) When it reaches the end of the segment, it must turn back (at no time) and keep watching the line.
How many watchdogs does it need to guarantee that the line segment is watched at all time? And how (initial positions and speeds of the dogs)?
Note:
It's clear that two dogs are not enough. I conjecture that four will suffice and three will not. For example, the below configuration doesn't work from 7.5 second if AB
's length is 10 meters.
Dog 1 at A walks to the right with speed 1.0 m/s
Dog 2 at between A and B walks to the right with speed 1.0 m/s
Dog 3 at B walks to the left with speed 1.0 m/s
Or it can be illustrated as:
A ---------------------------------------- B
0.0 sec 1 --> 2 --> <-- 3
2.5 sec 1 --> <-- 32 -->
5.0 sec <-- 31 --> <-- 2
7.5 sec <-- 3 <-- 21 -->
Please provide your solutions, hints, or related problems especially in higher dimensions or looser conditions (watchdogs can walk with acceleration, etc.)