Guess a Number

davar55 · 2008-03-18, 18:17

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.

mdettweiler · 2008-03-18, 18:20

Sort of like a numerical hangman?

I guess that 0 is one of the numbers.

davar55 · 2008-03-18, 18:27

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).

mdettweiler · 2008-03-18, 18:58

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.

henryzz · 2008-03-18, 19:46

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?

davar55 · 2008-03-18, 19:51

Yes, as I understand it.

bsquared · 2008-03-18, 20:46

[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]

Uncwilly · 2008-03-18, 21:37

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.

Wacky · 2008-03-18, 22:17

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

fivemack · 2008-03-19, 14:51

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.

Wacky · 2008-03-19, 18:23

Quote:

Originally Posted by fivemack

Well, you get log_2(5) bits of information per challenge

Tom,
Please show how you determined this.

2008-03-18, 18:17	#1
davar55 May 2004 New York City 1000010001011₂ 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, 22:17	#9
Wacky Jun 2003 The Texas Hill Country 3²·11² 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I guess this is OPN-related	fivemack	Factoring	1	2017-01-05 17:55
Quick! Guess what the next LL residue will be!	NBtarheel_33	Lounge	10	2014-03-14 19:14
I guess my computer is getting old...	ixfd64	Hardware	3	2009-03-05 13:20
Guess my IQ	10metreh	Lounge	7	2008-12-29 20:34
Guess the Polynomial	Kevin	Puzzles	15	2007-09-25 17:22

2008-03-18, 18:27	#3
davar55 May 2004 New York City 5×7×11² 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, 19:46	#5
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 13541₈ 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·11² 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-19, 14:51	#10
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14465₈ 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.