wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> What is my name?
        
(Message started by: Cool_Joh on Jun 24^th, 2007, 7:38pm)

Title: What is my name?
Post by Cool_Joh on Jun 24^th, 2007, 7:38pm

Assume that you don't know my name.
I tell you that my name consists of five different letters. You want to know my name, you may ask some yes/no questions.

What is the quickest way to get my name?
What should you ask?
What is the least number of questions should you ask?

Title: Re: What is my name?
Post by Obob on Jun 24^th, 2007, 9:17pm

If your name is just an arbitrary string of 5 letters (doesn't matter if it is a standard English name or whatnot) then there are 26 * 25 * 24 * 23 * 22 = 7893600 possible names. Enumerate these however you like, and write the corresponding numbers in base 2. Since log_2 (7893600) = 22.9123, we can view these numbers as having 23 bits. Now ask 23 yes/no questions to determine each binary digit under this correspondence, and we have the name.

Conversely, you can not ask fewer than 23 questions in the worst case scenario, since 22 questions is not enough to specify every integer smaller than 7893600.

If the name is a standard English name from some list, then just enumerate all the valid possibilities and proceed with the same strategy.

Title: Re: What is my name?
Post by towr on Jun 25^th, 2007, 1:42am

You could use three-valued questions; that is to say, some yes-no questions can't always be answered.
Just pick a name/number randomly from the middle third of the range, and without telling what that name is (but divulging it is randomly picked from the range) ask if his name comes later (or earlier).
If it's inside the middle range, he can't know and can't answer yes or no, which also provides information.

Title: Re: What is my name?
Post by Grimbal on Jun 25^th, 2007, 2:33am

"Do you agree to tell me your name right now or are you answering no to this question?"

Title: Re: What is my name?
Post by FiBsTeR on Jun 25^th, 2007, 8:37am

on 06/24/07 at 21:17:41, Obob wrote:

Enumerate these however you like, and write the corresponding numbers in base 2. Since log_2 (7893600) = 22.9123, we can view these numbers as having 23 bits. Now ask 23 yes/no questions to determine each binary digit under this correspondence, and we have the name.
[...]
If the name is a standard English name from some list, then just enumerate all the valid possibilities and proceed with the same strategy.

I had the same idea, but then I thought, not to be too picky at details, how is the person whose name you are trying to find going to know how you have enumerated the names? Or is that inherent to the question (e.g you would ask "If I ordered the names alphabetically and assigned each..., is the first bit of your name enumerated in this system...?")?

Title: Re: What is my name?
Post by towr on Jun 25^th, 2007, 8:48am

on 06/25/07 at 08:37:10, FiBsTeR wrote:

You can just as ask whether it comes before a certain name alphabetically. A name you pick for its position in your total list of all possible names.

Title: Re: What is my name?
Post by FiBsTeR on Jun 25^th, 2007, 8:55am

Ahh, oops, I took the system too literal, never thought to translate the system into one that would make the questions easier.

Title: Re: What is my name?
Post by srn347 on Aug 28^th, 2007, 12:09pm

I ask is the first letter a? Is it b?... Same for the second. No more that 125 questions. I might get it in 5 questions though.