Author |
Topic: Can you find out the Miss World phone number? (Read 3868 times) |
|
wonderful
Full Member
Posts: 203
|
 |
Can you find out the Miss World phone number?
« on: Mar 24th, 2008, 11:34pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Mar 24th, 2008, 11:42pm by wonderful » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Can you find out the Miss World phone number?
« Reply #1 on: Mar 25th, 2008, 2:06am » |
Quote Modify
|
Use error encoding
I think that gives us 22, 17+5; not 100% sure though, might be one more or less.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you find out the Miss World phone number?
« Reply #2 on: Mar 25th, 2008, 3:02am » |
Quote Modify
|
For the riddle where she can lie in at most one answer towr's method is optimal:
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?".
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) 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.
|
| « Last Edit: Mar 25th, 2008, 3:03am by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Can you find out the Miss World phone number?
« Reply #3 on: Mar 25th, 2008, 1:28pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you find out the Miss World phone number?
« Reply #4 on: Mar 25th, 2008, 3:39pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you find out the Miss World phone number?
« Reply #5 on: Mar 25th, 2008, 4:25pm » |
Quote Modify
|
What may be surprising ... if I give all questions at the same time, they will not depend on her phone number.
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 ( log2(99999-10000) +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.
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.
|
| « Last Edit: Mar 26th, 2008, 11:15am by Hippo » |
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you find out the Miss World phone number?
« Reply #6 on: Mar 25th, 2008, 4:32pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you find out the Miss World phone number?
« Reply #7 on: Mar 25th, 2008, 5:19pm » |
Quote Modify
|
Hippo: can you modify the question 2, 3, 4 in the given example for the simplified cases? It seems to have typos.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you find out the Miss World phone number?
« Reply #8 on: Mar 26th, 2008, 11:11am » |
Quote Modify
|
on Mar 25th, 2008, 5:19pm, 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?
|
|
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you find out the Miss World phone number?
« Reply #9 on: Mar 26th, 2008, 7:55pm » |
Quote Modify
|
It seems that you asked the question " Is your number among 2,4?" more than once. Can you clarify this.
Have A Great Day!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Can you find out the Miss World phone number?
« Reply #10 on: Mar 27th, 2008, 12:05am » |
Quote Modify
|
on Mar 26th, 2008, 7:55pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Can you find out the Miss World phone number?
« Reply #11 on: Mar 27th, 2008, 12:12am » |
Quote Modify
|
on Mar 25th, 2008, 4:25pm, 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 Mar 26th, 2008, 7:55pm, 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.
|
| « Last Edit: Mar 28th, 2008, 4:07am by Hippo » |
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: Can you find out the Miss World phone number?
« Reply #12 on: Mar 27th, 2008, 7:00pm » |
Quote Modify
|
Thanks Towr and Hippo. That really helps.
Have A Great Day!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print