mersenneforum.org Guess a Number
 Register FAQ Search Today's Posts Mark Forums Read

 2008-03-18, 18:17 #1 davar55     May 2004 New York City 10000100010112 Posts Guess a Number There's a hidden 10-digit 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 simple-minded 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 n-digit numbers on a k-digit alphabet, even better.
 2008-03-18, 18:20 #2 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 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 2008-03-18 at 18:21
 2008-03-18, 18:27 #3 davar55     May 2004 New York City 5×7×112 Posts Each guess is itself a 10-digit 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).
2008-03-18, 18:58   #4
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by davar55 Each guess is itself a 10-digit 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).
Ah, I see.

 2008-03-18, 19:46 #5 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 135418 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?
 2008-03-18, 19:51 #6 davar55     May 2004 New York City 5·7·112 Posts Yes, as I understand it.
 2008-03-18, 20:46 #7 bsquared     "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]
2008-03-18, 21:37   #8
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

32·1,171 Posts

Quote:
 Originally Posted by henryzz 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?
Yes, the "black pegs only" variant.

Last fiddled with by Uncwilly on 2008-03-18 at 21:39

 2008-03-18, 22:17 #9 Wacky     Jun 2003 The Texas Hill Country 32·112 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 n-1 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
 2008-03-19, 14:51 #10 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 144658 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.
2008-03-19, 18:23   #11
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 Originally Posted by fivemack Well, you get log_2(5) bits of information per challenge
Tom,
Please show how you determined this.

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Factoring 1 2017-01-05 17:55 NBtarheel_33 Lounge 10 2014-03-14 19:14 ixfd64 Hardware 3 2009-03-05 13:20 10metreh Lounge 7 2008-12-29 20:34 Kevin Puzzles 15 2007-09-25 17:22

All times are UTC. The time now is 15:52.

Fri May 27 15:52:03 UTC 2022 up 43 days, 13:53, 1 user, load averages: 2.07, 2.02, 1.94