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

  • $\begingroup$ may a dogh look past another dog in front of him? $\endgroup$ – mau Jul 29 '10 at 9:17
  • $\begingroup$ Yes, a dog may look past other dogs. $\endgroup$ – puri Jul 29 '10 at 9:51
  • $\begingroup$ This is a fun one :D $\endgroup$ – BBischof Jul 30 '10 at 7:06
  • $\begingroup$ Another ?small? generalization is to put some corners. Dogs must turn corners. $\endgroup$ – BBischof Jul 30 '10 at 7:12

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.

| cite | improve this answer | |
  • $\begingroup$ True, I guess. So basically this is like placing the dogs equally on 2-unit line segment (back and forth). Do you know any related problems or ideas to generalize this problem? $\endgroup$ – puri Jul 29 '10 at 9:59
  • 1
    $\begingroup$ No, I don't. However I could suggest the following generalization. Suppose now dogs are moving with constanst velocities inside unit square on a plane. And each dog can see points in "front" of it (it could see a point if it forms an angle smaller than 60 degrees with it's velocity vector). How many dogs enough to watch all square? $\endgroup$ – falagar Jul 29 '10 at 10:09
  • $\begingroup$ What restrictions on Dog's paths? Only coordinate directions? Only straight lines? Oh and the trivial solution is two doggies not moving at opposite corners. $\endgroup$ – BBischof Jul 30 '10 at 7:10

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.