7
$\begingroup$

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

  • 0
    may a dogh look past another dog in front of him?2010-07-29
  • 0
    Yes, a dog may look past other dogs.2010-07-29
  • 0
    This is a fun one :D2010-07-30
  • 0
    Another ?small? generalization is to put some corners. Dogs must turn corners.2010-07-30

2 Answers 2

9

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
    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?2010-07-29
  • 1
    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?2010-07-29
  • 0
    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.2010-07-30
4

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.