wu :: forums - Print Page


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

        riddles >> medium >> celebrity search
        
(Message started by: almost dead on Jun 5^th, 2008, 7:52pm)

Title: celebrity search
Post by almost dead on Jun 5^th, 2008, 7:52pm

There are N people in a room and one of them is a celebrity. Everybody knows at least the celebrity while the celebrity knows no one. You enter the room to find the celebrity. You are only allowed to pick a person, point to another person, and ask whether the first person knows the second one. How will you find the celebrity in minimum number of questions?

Title: Re: celebrity search
Post by towr on Jun 6^th, 2008, 12:33am

This can be treated as a graph problem; like this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1195383906;) and this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1121165636;) thread from the CS section. (The last post in the latter thread gives a good approach [hide]If you ask A whether he knows B, then on yes, you eliminate A as celebrity, on no you eliminate B[/hide])