Finding the Celebrity at a Party: A Mathematical Induction Approach?

  • Thread starter issacnewton
  • Start date
In summary, the problem is to find a celebrity at a party of n people by asking only questions about whether one person knows another. Using mathematical induction, it can be shown that the minimum number of questions needed to find the celebrity is 3(n-1). The base case of n=2 requires only 2 questions, but the problem states that 3 questions must be asked, so there may be an error in the problem. It is also assumed that the person asking the questions is not included in the n people at the party. The hint given involves asking one question to eliminate one person as a celebrity, using the inductive hypothesis to identify a potential celebrity, and then asking two more questions to determine if that person is actually the
  • #1
issacnewton
1,041
37
Here is a problem

A guest at a party is a celebrity if this person is known
by every other guest, but knows none of them. There is at
most one celebrity at a party, for if there were two, they
would know each other. A particular party may have no
celebrity. Your assignment is to find the celebrity, if one
exists, at a party, by asking only one type of question-
asking a guest whether they know a second guest. Everyone must
answer your questions truthfully. That is, if Alice
and Bob are two people at the party, you can ask
Alice whether she knows Bob; she must answer correctly.
Use mathematical induction to show that if there are n
people at the party, then you can find the celebrity, if there
is one, with 3(n - 1) questions. [Hint: First ask a ques-
tion to eliminate one person as a celebrity. Then use the
inductive hypothesis to identify a potential celebrity. Fi-
nally, ask two more questions to determine whether that
person is actually a celebrity.]

Now, for the base case I took n=2. Suppose I ask Alice
if she knows Bob and then I ask Bob if he knows Alice.
There are four possible combinations of answers. Let Y be
'yes' and N be 'no'. So possibilities are YY,YN,NY,NN.
In the first case, both know each other , so nobody is
celebrity. In the second case, Bob is celebrity.In the
third case, Alice is celebrity. In the last case,
again nobody is celebrity. So to determine the celebrity
at this party, I had to ask only two questions. But according
to the problem, for the n=2 case, 3 questions need to be
asked. Is there something wrong with the problem. Also
I am assuming that when I am the one who is asking all
these questions at the party, I am not included among
these n persons. Is that a fair assumption ?

Also I could not understand the hint..

Thanks
 
Physics news on Phys.org
  • #2
Use mathematical induction to show that if there are n
people at the party, then you can find the celebrity, if there
is one, with 3(n - 1) questions.

This is confusing English, it means you must show that 3(n-1) questions are sufficient to find the celebrity.
 
  • #3
I think [tex]3(n-1)[/tex] are the minimum no of questions which I need to ask.
So can you see if the problem is wrong or I am wrong ?
 

FAQ: Finding the Celebrity at a Party: A Mathematical Induction Approach?

How do you find a celebrity at a party?

Finding a celebrity at a party can be a bit tricky, but there are a few strategies that can increase your chances. One way is to keep an eye out for any announcements or social media posts about celebrity guests beforehand. Another option is to look for areas where celebrities are more likely to be, such as VIP sections or areas near the stage or DJ booth. Additionally, networking and making connections with event organizers or people who know the celebrity can also help.

Is it appropriate to approach a celebrity at a party?

It is generally considered polite to respect a celebrity's privacy and personal space at a party. However, if you do happen to come across a celebrity and want to approach them, it's important to be respectful and considerate. Remember that they are also there to enjoy themselves and may not want to be constantly approached by fans. If you do approach them, be brief, polite, and avoid interrupting any conversations they may be having.

What should I do if I want to take a photo with a celebrity at a party?

If you want to take a photo with a celebrity at a party, it's best to ask for their permission first. Approach them politely and ask if they would be willing to take a photo with you. Keep in mind that they may decline or may not want to take photos at all, so it's important to respect their decision. If they do agree, make sure to take the photo quickly and thank them afterward.

How can I make a good impression on a celebrity at a party?

First and foremost, it's important to be respectful and considerate of a celebrity's time and personal space. Avoid bombarding them with questions or requests, and instead try to have a genuine conversation if the opportunity presents itself. It's also a good idea to have some knowledge about the celebrity beforehand so you can discuss their work or interests. Additionally, being friendly, confident, and polite can help make a good impression.

Are there any rules or etiquette I should follow when interacting with a celebrity at a party?

Yes, there are a few general rules and etiquette to keep in mind when interacting with a celebrity at a party. First, always be respectful and polite. Avoid being too pushy or invasive, and remember to ask for permission before taking any photos. It's also important to be mindful of their time and space, as they may have other commitments or may not want to be constantly approached by fans. Lastly, try to have a genuine and respectful conversation rather than just asking for favors or autographs.

Similar threads

Cryptography - coin flipping protocol
Replies
3
Views
988
Prove this inequality using induction
Replies
2
Views
585
Finding Number of Handshakes in a Party
Replies
1
Views
1K
I A popular explanation of Bell's inequalities
Replies
16
Views
2K
Proof by Induction of String exponentiation? (Algorithms)
Replies
5
Views
1K
N-dimensional broken stick problem -- find joint density
Replies
3
Views
681
A Is there still a collapse problem after decoherence?
Replies
7
Views
1K
Understand Public Key Encryption
Replies
8
Views
2K
How Many People Needed for a 50% Chance of Shared Birthday Months?
Replies
2
Views
9K
I How things appear to an accelerated observer
3
Replies
70
Views
4K

Hot Threads

Recent Insights

Back
Top