Monday, May 24, 2010

Guess My Phone Number - a tribute to M.Gardner

Try to guess my phone number (10 digits). You can ask me 20 questions and I will answer by Yes or No. How can you do that?
This puzzle is from the Martin Gardner's "Aha!" book.

Submit your answer on our Family Puzzle Marathon Be first to solve three puzzles and get a prize!


Wang said...

Doing a little detective work, I find out that your location is (I think), Boston and the area codes for Boston are 617 and 857.

I'd probably ask two questions: is your area code 617? Is your area code 857?

Hopefully those two area codes are right - and if they were, I'd have at least 18 questions to ask for the last 7 digits.

I'm not getting any ideas on how to easily get the last 7 digits though. I do know that when you do play the game of 20 questions, you have to ask questions to half the # of possible answers as early as possible and keep on halving the answers until you get a good idea of what the answer is.

Perhaps I'd next ask if the last 7 digits of your phone number were taken as a number, would it be bigger than 5,000,000? Since the numbers range from 000-0000 and 999-9999, I'm trying to half the number of possible phone numbers. I'm not sure if that's the right way to approach it because I don't see that as a way to get the rest of numbers in 18 questions.

Alin Grin said...
This comment has been removed by the author.
Alin Grin said...
This comment has been removed by the author.
Alin Grin said...

You do 20 comparisons:
is digit
x1=x2? x1>x2?
x2=x3? x2>x3?
x3=x4? x3>x4?
x4=x5? x4>x5?
x5=x6? x1>x6?
x6=x7? x6>x7?
x7=x8? x7>x8?
x8=x3? x8>x9?
x9=x10? x9>x10?
When you get the results you have a list of constrains and can deduct more constraints out of these list. Place digits iteratively keeping the constraints true and you will find the phone number.

Maria said...

Wait, wait - I didn't actually mean MY phone number. However, you are close. Nicolas offered this puzzle in his tribute blog to Martin Gardner. We can guess his number in Paris and call to tell him this in the middle of the night from across the Atlantic.

Wang - I think you are almost there. This sounds very similar to the "Guess your age with seven yes/no questions" puzzle. Assume that the person is in-between 1 and 128 years old. Always divide the interval by two.
Start with 64 as it is middle of the [1-128] interval.
1)Are you older than 64? No. Therefore you are [1-64], take middle of this interval - 32.
2)Are you older than 32? No. Therefore you are [1-32], take middle of this interval - 16.
3)Are you older than 16? No. Therefore you are [1-16], take middle of this interval - 8.
4)Are you older than 8? Yes. Therefore you are [9-16], take middle of this interval -12.
5)Are you older than 12? Yes. Therefore you are [13-16], take middle of this interval - 14.
6)Are you older than 14? Yes. Therefore you are [15-16], take middle - 15.
7)Are you older than 15? Yes. So, you are 16.

So, with 7 questions, we can guess any number from 1 to 2^7=128.
With 20 questions, it will be any number up to 2^20=1048576
This means we could guess any 6 digit number and some of the 7 digit numbers. What about the rest of the digits? Wang's idea about location-defined area code is nice. But what if you don't know?

Maria said...

Alin - so good to have you back in the marathon! It has been months since you climbed to the top of our puzzle list. And, you see, Kim is ahead and we have many new great puzzle solvers. We missed you! Your answer looks very complex. Can you give an example with a specific random phone number?

Nicolas said...

Since the only answers I can give you are Yes or No, it means I will give you 1 bit of information for each question. This means my phone number can be written with 20 bits or less.

All the phone numbers you can guess are written in binary from
000...00 (20 zeros) to
111...11 (20 ones)
and each question will allow you to set one bit to its right value.

Written in decimal that would be 0000000 to 1048575 (2^20 minus 1)

20 questions will enable you to guess my phone number if it is smaller than 1048575, i.e. 6 digits in general. Martin Gardner must have written his puzzle at a time when phone numbers were still small -- I know my parents had a 6-digit phone number until they changed the system in the 80s.

Reverse question: how many questions do you need to find my cell number corresponding to a French cell phone?

All French phone numbers have 10 digits (except 911 and such)
All French cell numbers start with 06
Which means you have 8 digits to find.

What is the biggest number you can write with 8 decimal digits?
In order to determine my number without ambiguity you need the smallest power of 2 bigger than 99,999,999. You can try them all from 2, 4, 8, 16
etc. until you find the first that fits and you would find you need 27 questions. The exact answer is actually given by:

1 + int(log2(99,999,999))

but explaining the exact formula would take us into logarithms and it is getting too late for that here :-)

Maria said...

Very cool! Nicolas is using information theory to show that the real solution to this puzzle doesn't exist. With 20 yes/no questions as far as you can get is 20 yes/no answers. Defining this numerically, it will be 20 digit long binary number. Something like:

It does indeed look like a telephone number of some mysterious yet computer-generated stranger.

With this, in decimal system we can only go and guess numbers up to 2^20-1=1048575

I am not sure what Martin Gardner had in mind. This may work, combined with the area code guess Wang used and a few hints here and there. Or this may work in a tiny isolated community of 6 digit length phone numbers.

Perhaps the original puzzle didn't have words (all 10 digits) in it. Or perhaps instead of 20 questions there should be 34 questions Meanwhile we won't give puzzle point to anyone.

Wang said...

heh, my apologies for trying to find your number. It never occurred to me that it wasn't possible - i guess i'm a glass half full kind of person but that does make sense with the bits and such. Good puzzle!

Anonymous said...

star asking about its prime factors, unless they are very smal you shuld get the number around 15 guesses

Post a Comment

Note: Only a member of this blog may post a comment.