20080318, 18:17  #1 
May 2004
New York City
1000010001011_{2} Posts 
Guess a Number
There's a hidden 10digit number (leading zeros significant) which
has to be determined. You are allowed to make guesses, for each of which you are told the exact number of digit matches. The object is to guess the number in as few guesses as possible. The puzzle is to devise a simple strategy that bounds the number of guesses needed, regardless of the hidden value. The smaller the bound, the better the strategy. Obviously, a simpleminded enumeration works, but has a high bound. If you can find an optimal strategy, that's great, but for this puzzle simplicity of description is also a goal. If the same strategy gives a "low" bound for the general case of ndigit numbers on a kdigit alphabet, even better. 
20080318, 18:20  #2 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 
Sort of like a numerical hangman?
I guess that 0 is one of the numbers. Last fiddled with by mdettweiler on 20080318 at 18:21 
20080318, 18:27  #3 
May 2004
New York City
5×7×11^{2} Posts 
Each guess is itself a 10digit number, for which you are told
the number of exact position matches. So for example, if the hidden number is 1234500000 and you guess 1243900777, you are told "4" (for the 12xxx00xxx that match exactly). 
20080318, 18:58  #4 
A Sunny Moo
Aug 2007
USA (GMT5)
3·2,083 Posts 

20080318, 19:46  #5 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
13541_{8} Posts 
am i right in saying it is the same as mastermind with 10 colours and 10 places except that u dont get told how many colours are right but not in the right places?

20080318, 19:51  #6 
May 2004
New York City
5·7·11^{2} Posts 
Yes, as I understand it.

20080318, 20:46  #7 
"Ben"
Feb 2007
3,617 Posts 
[SIZE=2]First 10 guesses: Here is a simple strategy to get the ball rolling which has an upper bound of 100 guesses. I doubt it's optimal... [SIZE=2]0000000000[/SIZE] [SIZE=2]1111111111[/SIZE] [SIZE=2]...[/SIZE] [SIZE=2]9999999999[/SIZE] [SIZE=2]this will tell you how many of each digit are used, but nothing about their location.[/SIZE] [SIZE=2]Next, assuming there is a digit that is used 0 times (represented here as X), guess:[/SIZE] [SIZE=2]X000000000[/SIZE] [SIZE=2]0X00000000[/SIZE] [SIZE=2]...[/SIZE] [SIZE=2]000000000X[/SIZE] [SIZE=2]then,[/SIZE] [SIZE=2]X111111111[/SIZE] [SIZE=2]1X11111111[/SIZE] [SIZE=2]...[/SIZE] [SIZE=2]111111111X[/SIZE] [SIZE=2]etc, for all digits except X[/SIZE] [SIZE=2]each guess's result which is 1 less than the result obtained by guessing all 10 positions being the same digit reveals the proper position of that number. the maximum number of guesses for this process is 90, so the total upper bound for guesses is 100. Again, this assumes there is a digit which is not used in the secret number, X, to use as a 'location mask'.[/SIZE] [SIZE=2]If all numbers are used once, then the same procedure could be used by picking an arbitrary digit as the mask. Now, it is possible for, say,[/SIZE] [SIZE=2]X000000000, to produce a result 1 greater than[/SIZE] [SIZE=2]0000000000, if X happens to be an exact match. If this is the case, we've learned one position in less time than the naive method above would have done, and we can pick a new mask digit and continue. So the upper bound is less than 100 guesses, but I haven't figured out exactly what it is yet.[/SIZE] [/SIZE] 
20080318, 21:37  #8 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
3^{2}·1,171 Posts 
Yes, the "black pegs only" variant.
Last fiddled with by Uncwilly on 20080318 at 21:39 
20080318, 22:17  #9 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
34 tries
First note that it takes only (at most) 9 tries to get the 10 counts (the last by subtraction)
Now, we can eliminate 2 digits at a time with n1 tries. Pick 1 digit as the "background" and another as the test digit. For each "probe", there are three possible results. If the count is less than the background count, you have located a place for the background digit. If it is greater, it is the location of the probe digit. ANd if it is the same, it is something else. After eliminating those two digits, pick two more and repeat. In the worst case, each digit occurs exactly once and the background and probe digits are in the last two places tested. 9 (to get the counts) +9 (to place "0" and "1") +7 (for "2" and "3") +5 +3 +1 =34 
20080319, 14:51  #10 
(loop (#_fork))
Feb 2006
Cambridge, England
14465_{8} Posts 
Well, you get log_2(5) bits of information per challenge, and are trying to explore a log_2(10^10) problem space, so you can't guarantee success in less than 14 moves. This isn't a very helpful lower bound.
There's an optimal strategy for Mastermind at http://www.tnelson.demon.co.uk/mastermind/table.html but it's pretty opaque. 
20080319, 18:23  #11 
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I guess this is OPNrelated  fivemack  Factoring  1  20170105 17:55 
Quick! Guess what the next LL residue will be!  NBtarheel_33  Lounge  10  20140314 19:14 
I guess my computer is getting old...  ixfd64  Hardware  3  20090305 13:20 
Guess my IQ  10metreh  Lounge  7  20081229 20:34 
Guess the Polynomial  Kevin  Puzzles  15  20070925 17:22 