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

        riddles >> hard >> Can you find out the Miss World phone number?
        
(Message started by: wonderful on Mar 24th, 2008, 11:34pm)
Title: Can you find out the Miss World phone number?
Post by wonderful on Mar 24th, 2008, 11:34pm
The Miss world phone number is a five digit number. You have the opportunity to know this number by asking her a series of questions. She will answer "yes" or "no". She would tell lie in one and only one answer she gave you.

For instance, if her phone number is 15905. Your first question was  is this number is divisible by 5. Her answer was "no". She then would tell you the truth in responding to all your remaining questions.

What is the minimum questions to  find out her number?  
Title: Re: Can you find out the Miss World phone number?
Post by towr on Mar 25th, 2008, 2:06am
[hide]Use error encoding

I think that gives us 22, 17+5; not 100% sure though, might be one more or less.[/hide]
Title: Re: Can you find out the Miss World phone number?
Post by Hippo on Mar 25th, 2008, 3:02am
For the riddle where she can lie in at most one answer towr's method is optimal:
[hide]find encodding of all possible numbers (probbaly 10000 to 99999), but works as well for 00000 to 99999 usins as small fixed number k of bits as possible such that any two codes differ in at least 3 bits so their one bit neighbourhoods can be distinguished. In i-th question give here list of numbers whose i-th bit in encodding is set and ask her "Is your number on the list?".[/hide]

But if she must lie in one answer, she should know all the questions in advance or you can stop asking her questions and
declare her to be a cheater ... forcing her to lie answering the first question.

In such case (all questions in advance, exactly one lie) [hide]The condition on encoddings changes that neighbourhoods differing by exactly one bit should differ. The code distances greater than 3 are still OK, but several code pairs can be at distance 1 now. Actually the codes with even number of ones are independent on codes with odd number of ones now.[/hide]
Title: Re: Can you find out the Miss World phone number?
Post by Grimbal on Mar 25th, 2008, 1:28pm
Hm...

You could start by asking: "Is your first answer negative?".  She has to lie.  Then you just need 17 more questions.

Or your second question could be "Is the answer to this question positive if and only if you accept to give me your phone number right now?".

Whether she says yes or no, she has to give you her phone number or she would have lied.  And she cannot give you a wrong number, that would be a lie.
Title: Re: Can you find out the Miss World phone number?
Post by wonderful on Mar 25th, 2008, 3:39pm
Great! I think you all had a right and interesting approach. To help the readers have a better understanding of your answer, can you make it a bit clearer?

For instancce, if her number is 10000 what will be your questions? Just a few questions to illustrate will be sufficient.

Have A Great Day!
Title: Re: Can you find out the Miss World phone number?
Post by Hippo on Mar 25th, 2008, 4:25pm
What may be surprising ... if I give all questions at the same time, they will not depend on her phone number.

[hide]Actually in the encodding for exactly one lie we are looking for codes with distance at least 4 with fixed parity of ones. Together with this set there is twin set which can be obtained by say negating the last bit. It seemed to me we will need to add 6 control digits obtaining (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(99999-10000)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif+6)-1=22 digits = 22 questions. I would guess Eigenray will give you a correct polynomial which will compute the 6 digits from the original 16. I am not as good in algebra as him.[/hide]

Smaller example ... suppose she can have 4 possible numbers 1,2,3,4 ... encode them as 0000,1111,0001,1110 and the set of questions would be
1 according the last code digit) Is your number among 2,3?
2 according the 2nd last code digit) Is your number among 2,4?
3 according the 3rd last code digit) Is your number among 2,4?
4 according the first code digit) Is your number among 2,4?
If odd number of answers woud by yes, the number is either 1 or 2 otherwise it's 3 or 4.
Suppose the former case ... if 3 answers are yes, it's 2, otherwise it's 1.
In the latter case negate the answer for the first question and if after that among the answers are 3 answers yes it's 4, otherwise it's 3.

Yes the reasoning for this degenerated case with repeated questions can be easier (we can trivially deduce which answer was lie), but the mentioned correspond to philosophy for biger sets.
Title: Re: Can you find out the Miss World phone number?
Post by wonderful on Mar 25th, 2008, 4:32pm
Excellent Hippo! Your explanation is very well-done and will certainly help those with little CS knowledge appreciate the solution better.

Have A Great Day!
Title: Re: Can you find out the Miss World phone number?
Post by wonderful on Mar 25th, 2008, 5:19pm
Hippo: can you modify the question 2, 3, 4 in the given example for the simplified cases? It seems to have typos.
Title: Re: Can you find out the Miss World phone number?
Post by Hippo on Mar 26th, 2008, 11:11am

on 03/25/08 at 17:19:48, wonderful wrote:
Hippo: can you modify the question 2, 3, 4 in the given example for the simplified cases? It seems to have typos.


Which typos do you point at?
Title: Re: Can you find out the Miss World phone number?
Post by wonderful on Mar 26th, 2008, 7:55pm
It seems that you asked the question " Is your number among 2,4?" more than once. Can you clarify this.

Have A Great Day!
Title: Re: Can you find out the Miss World phone number?
Post by towr on Mar 27th, 2008, 12:05am

on 03/26/08 at 19:55:00, wonderful wrote:
It seems that you asked the question " Is your number among 2,4?" more than once. Can you clarify this.
That's to find out her lie. If the last three questions get the same answer, then she lied about the first; otherwise the one out of three that's different is the lie.
Title: Re: Can you find out the Miss World phone number?
Post by Hippo on Mar 27th, 2008, 12:12am

on 03/25/08 at 16:25:52, Hippo wrote:
Yes the reasoning for this degenerated case with repeated questions can be easier (we can trivially deduce which answer was lie), but the mentioned correspond to philosophy for biger sets.



on 03/26/08 at 19:55:00, wonderful wrote:
It seems that you asked the question " Is your number among 2,4?" more than once. Can you clarify this.

Have A Great Day!


Already done.

BTW: I suppose there exists another encodding for four numbers not having this property (oops 2 must be same, but at least you will not find which one is lie so trivially).
Encodding scheme for bigger sets will not have the property.
Title: Re: Can you find out the Miss World phone number?
Post by wonderful on Mar 27th, 2008, 7:00pm
Thanks Towr and Hippo. That really helps.
Have A Great Day!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board