Watchdog Problem

508 Views Asked by At

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.)

2

There are 2 best solutions below

3
On BEST ANSWER

Three dogs is enought I think.

Let the length of line segment be equal to 1 (with coordinates from 0 to 1).
First dog: start position = 0, speed = +1/3
Second dog: start position = 2/3, speed = +1/3
Third dog: start position = 2/3, speed = -1/3

After 1 second the position becomes similar.

0
On

I'll make the trivial answer: 1 dog at point A, facing point B, walking with a velocity of 0. Presumably, you should really highlight that the dogs' velocities must be non-zero...this is the kind of side case that math people love to exploit.