wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Guards
        
(Message started by: R on Mar 18^th, 2010, 9:38pm)

Title: Guards
Post by R on Mar 18^th, 2010, 9:38pm

57 security guards are positioned so that no two pairs of guards are the same distance apart. Every guard watches the guard closest to him. Is there an arrangement of the guards so that every guard is being watched?

Title: Re: Guards
Post by towr on Mar 19^th, 2010, 2:41am

[hide]If you have a series of guards where A watches B watched C etc, then each distance from one to the next is smaller, which means that last one cannot be watching A, because then A would also watch him.
So with the exception of isolated pairs of agents we have a graph without cycles). Which means the graph is a collection of pairs and trees, and in the trees the leaves are unwatched.[/hide]

Title: Re: Guards
Post by Grimbal on Mar 19^th, 2010, 3:02am

[hide]And with an odd number of guards, you can not have only 2-cycles (bi-cycles?). [/hide]