A little puzzle/quiz

**hammer** · 12-05-2004, 10:59 PM

Lets say that you need to guess someone's phonenumber (9 digits) by asking him questions of which the answer is only "yes" or "no".
How many minimum questions do you need to ask him to get the right number:
a) 7; b) 9; c) 512; d) 100000;

**Harry Hunt** · 13-05-2004, 12:41 PM

I'd say the absolute minimum is 1, "Is your phone number 219483759", "yes!"...

If you ask for each individual digit seperately and get them all right at the first try, you'd have to ask 9 questions "Is the first digit 2", "yes"....

**cairnswm** · 13-05-2004, 01:40 PM

I think the Question is "What is the minimum number to find out for certain what someones phone number is (a nine digit phone number)?"

Is your Phone number less than 500 000 000?

If Yes then

Is your phone number greater than 250 000 000?

If Yes then

Is your phone number greater than 375 000 000?

etc

The minimium number to ask to find out what it is is then 30. (I think its supposed to be 32 but my calculator says 30)

**hammer** · 14-05-2004, 01:06 PM

cairnswm you can ask whatever questions you want the only condition is that they can be answered with "yes" or "no"

the idea is that you think of an algorithm that will ALLWAYS get the right answer with 7, 9, 512 or 100000 tries

**peterbone** · 28-05-2004, 11:34 AM

I'd agree with cairnswm - it's 30. Convert 999999999 to binary and there are 30 digits. You can then just ask if each digit of the binary number is a 1.

Peter

**lithander** · 28-05-2004, 03:37 PM

how is your cellphonenumber structured? in germany we have 11 digits but the first 2 are identicall for every cellphone. So if that is the same in bulgaria only 7 digits would have to be found out, which results in 24 question...

An other idea: The first 4 digits name the provider and net so you have only a quite small variation there. This could be used to save some more questions...

-lith