Author |
Topic: celebrity search (Read 418 times) |
|
almost dead
Newbie
Posts: 17
|
 |
celebrity search
« on: Jun 5th, 2008, 7:52pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: celebrity search
« Reply #1 on: Jun 6th, 2008, 12:33am » |
Quote Modify
|
This can be treated as a graph problem; like this and this thread from the CS section. (The last post in the latter thread gives a good approach If you ask A whether he knows B, then on yes, you eliminate A as celebrity, on no you eliminate B)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print