Rita, a columnist for the Daily Princetonian, is covering a party. Rita’s job is to identify a celebrity, if one exists. A celebrity is person that is known by every other person, but doesn’t know any of them. Rita asks questions to the guests of the following form: Excuse me. Do you know the person over there? Assume that all of the guests at the party are polite (even the celebrity) and answer any question with the correct answer. Explain how Rita can identify the celebrity using as few questions as possible.

Question

baseballer2014 · Answer

@dan815 @hero

dan815 · Answer

hmm how about asking someone if they know someone else, if yes then go to the other person and ask them if they know the person you just asked, if they say no then that's a celeb? otherwise they dont know each other, and are excluded from the list, if the first answer is No to begin with you should still go to ask the other person if they know the person you just asked, if yes then u asked the celeb if no then theyre both excluded

dan815 · Answer

probably wrong though theres a very bad assumption that people who know someone other than the celeb must be aquaintances

dan815 · Answer

@bswan how??

anonymous · Answer

well ur correct dan ,
if u asked do u know someone else 
if yes the its normal no its  the celeb

dan815 · Answer

lol :)

dan815 · Answer

look at my beautiful wannabe code

dan815 · Answer

let Guest={G0,G1,G2....Gn} , #list of guests with different indices
For n= 0:2:n
     A=Guest(n)
     B=Guest(n+1)
      ask person A : do you know person B
      {if yes:
               {Ask B: do you know A?
               if yes
                       Exclude both and ask 2 new people
               If no 
                       B is Celeb}

     {If no:
              {Ask B: Do you know A?
              if yes:
                       A is celeb, break
              if No:
                       Exclude both and ask 2 different people}
}

anonymous · Answer

nice work :D
u can draw algorithm hehe wanna try :P

anonymous · Answer

T_T

dan815 · Answer

that algorithm has all sorts of languages mixed in it lol...  i didnt learn any langueage well soo its all a jumble

dan815 · Answer

theres a bit of python influence... some java some matlab

dan815 · Answer

i write some silly programs in matlab :)

dan815 · Answer

do you know sudoku solver??

anonymous · Answer

i can solve sod by my self :P

dan815 · Answer

yes buut to make the computer do it for you it seems magical

anonymous · Answer

yeah right