1. There are 50 people in a party. Each person knows at least oneother person. A

Question

1.                 There are 50 people in a party. Each person knows at least oneother person. At some point a celebrity enters the party. Everybodyknows the celebrity but the celebrity knows no one. You are new intown and get to the party after the celebrity. You don’t knowanybody, including the celebrity. You want to figure out who thecelebrity is by asking questions of the form “Do you knowthis person?” (“This person" could be anyone you choosefrom the party.) How can you do this by asking at most 50questions?

Explanation / Answer

There are 51 people in the party (without counting yourself). We will write an algorithm that takes exactly 50 steps to find thecelebrity. Each step consists of asking the question“Do you know this person?” once anddeleting one person who is not the celebrity from the listof guests in the party. At the end, there is onlyone person on the list. This person is the celebrity. Step 1. Pick any two people at random, call them p0 and p1. Ask p1“Do you know this person?” pointing at p0. If p1answers no, then p0 is not the celebrity (everyone knows thecelebrity) and should be deleted from the list of guests. If p1answers yes, then p1 is not the celebrity (the celebrity knows noone) and should be eliminated from the list. Step k. (2 k 50) Suppose q is the person you decideto keep in step k 1. Pick another person at random who isstill in your list, say pk. (That is, a person to whom you have notasked questions.) Ask pk “Do you know this person?”pointing at q. As in step 1, if pk answers no, then q is not thecelebrity (everyone knows the celebrity) and should be deleted fromthe list of guests. If pk answers yes, then pk is not the celebrity(the celebrity knows no one) and should be eliminated from thelist. Enjoy :-)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.