(17 votes, average: 3.65 out of 5)There are (n+1) people in a party, they might or might not know each others names.
There is one celebrity in the group(total n +1 people), celebrity does not know any of n peoples by name and all n people know celebrity by name.
You are given the list of people’s names(n+1), You can ask only one question from the people. Do you know this name ?
How many maximum number of questions you need to ask to know the celebrity name?
Note: assume all names are unique. and you know the persons by name(but don’t know if he is celebrity)
Check your answer:-
Click here to See SolutionIf A knows B => A can not be a celebrity.
If A does not know B then B can not be a celebrity.
So you strike out one name from your list, so on each question you can reject one name.
When there are only two people left in the list, then you will ask first person, “Do you know the second person ?”. If he says yes then second person is the celebrity and if he says no then the first person is the celebrity.
Thus you need to ask a maximum of n questions to correctly figure out celebrity name.
On worst case it will take n(n+1)+n time to know the celebrity.
Please correct me, if Am wrong. Isn’t the answer – (n+1) or (n+1+2).
Ask n+1 questions to the same person to which the person says “he knows 1 or 2 of the names(one of celeb or celeb+himself). So if the person says he knows only one name, he is the celeb. Hence n+1 questions
But if he says that he knows 2 of the names, you may have to take out these 2 names and ask somebody else. So obviously they’d say that they know one of the 2 names, which will of course be the celeb’s name. Hence, (n+1)+2 questions.
(N+1)*(N+1) he has to ask each for each name in worst case celebrity will tell he knows him I mean himself
First of all the question has been asked for minimum number of questions and you have used the word maximum in the solution.
Second, you have assumed that the person who has the list of names knows who the people are. Let me put it this way, suppose there are 7 party animals there named Ashu Bablu Champu Dhanno Elaichi Fuddu Ghodu, one among them a celeb (conditions being same as mentioned in the question). And you ( suppose you are ACP Pdadyuman ) have a list with names of these animals (party animals), so dont assume that Pradyuman knows who is Ashu and who is Bablu and so on as it has not benn mentioned in the question.
I SUPPOSE YOU MIGHT THINK ABOUT AMENDING ONE AMONG QUESTION AND THE SOLUTION
Also the answer N+1 is not the minimum even if we go by your assumption that PRadyuman knows who is A B C D……
In the light of your assumption..
let the names are as A B C D E F G.
You will call A and ask him – do you know B.. and so on for rest of the people except A himself because of course he knows himself. And if A is himself the celebrity you only had to ask only 6 questions to conclude that A is the celeb because he will not recognise any of the 6 names.
So the minimum number of questions will be “n”
Hi Atul,
Suppose that “X” has been given n+1 names to figure out who is the celebrity. In your answer you have already assumed that X knows who is A. If that is not the case then X will ask “A” whether he knows “A”..if A says yes (and of course he will) then X will ask n-1 more questions to figure out whether A knows anyone else. In case X gets all the answers as “NO” then he will be not ask “A” about the n+1 th name. So the total question here is (1+n-1) and now “X” will pick any other person and ask only one question “does he know A?” if that person says yes then “A” is the celebrity(as two people know him) and if that person says “NO” it means A is not celebrity and the the person having n+1 th name is the celebrity.
So the total number of questions will be n+1.
Hi Buddy,
If we assume that “X” knows who A is then X knows that he can skip asking about A because he knows that A will recognise his/her name in the list. So he only needs to ask N questions and if A is a celebrity all N questions to A will be asnwered in a NO.
It will take less than quarter of a millisecond for X to know that A is the celebrity, because X knows that only a celeb is the one who will identify with 1 name only and will say NO for all guests in the party, all other guests in the party will identify atleast two names ( one of the celeb and other of themselves).
So in this SPECIAL case N questions are what all X require.
Hi Terminator,
Buddy there are N+1 people in the party and not N.
N+1= 7 here
A* B C D E F G (A being the celeb)
A– n n n n n n
If “X” knows who is A and who is B and all but dont know who is the celeb. Then X need not bother to ask about A from A and six Nos will do. “n”
For any other party guest other than the celeb, X needs only six questions.As X will ask A about B if A answers yes then A is not a celeb, if No then B is not a celeb. Then whether A or B is eliminated X can ask the other one about C and further eliminate one among A/B and C and so on it will take only Six questions.
Hence, only N questions for this case.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Lets go by your assumption that X does not know who is A and who is B and all… Since there are N+1 people in the party, X after being responded in a Yes by A for identifying with A, still needs to be asked N questions not N-1, because there are N+1 people in the party.
And in case A answers one Yes and N nays then ” N+1″ questions are all required by X in this case.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
😉 again,
Going by the question this time strictly..
1. X does not know who A or B and all is.
2. All other guests except the celeb may or maynot know each other, so lets take the situation that all guests know each other as well as the celeb but the celebrity does not know any of the people among guests.
Lets assume there are 7 guests A B C D E F G*(celeb)
N+1 = 7
A B C D E F G
A y y y y y y y
B y y y y y y y
C y y y y y y y
D y y y y y y y
E y y y y y y y
F y y y y y y y
G n n n n n n n y
So for “X” guests are numbered as 1,2,3,4,5,6,7 not in that order of course.
X will call lets say 1 and asks starting from A,
If, 1 is G then only six questions are enough. “N”
If, 1 is other than G, then what is the answer please explain…
Thanks Atul, i have corrected the question, its maximum number questions you need to ask. (Actually its the minimum as well, as you cant determine without asking n questions)
Also it is assumed that, you know every person by name, so you will not ask same person, do you know himself.