mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-03-18, 18:17   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2008-03-18, 18:20   #2
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

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
mdettweiler is offline   Reply With Quote
Old 2008-03-18, 18:27   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

423510 Posts
Default

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).
davar55 is offline   Reply With Quote
Old 2008-03-18, 18:58   #4
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

11000011010012 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
mdettweiler is offline   Reply With Quote
Old 2008-03-18, 19:46   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,969 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2008-03-18, 19:51   #6
davar55
 
davar55's Avatar
 
May 2004
New York City

5·7·112 Posts
Default

Yes, as I understand it.
davar55 is offline   Reply With Quote
Old 2008-03-18, 20:46   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×1,193 Posts
Default


[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]
bsquared is offline   Reply With Quote
Old 2008-03-18, 21:37   #8
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

29·349 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
Uncwilly is offline   Reply With Quote
Old 2008-03-18, 22:17   #9
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default 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
Wacky is offline   Reply With Quote
Old 2008-03-19, 14:51   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22·32·179 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2008-03-19, 18:23   #11
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by fivemack View Post
Well, you get log_2(5) bits of information per challenge
Tom,
Please show how you determined this.
Wacky is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:20.


Mon Dec 6 06:20:19 UTC 2021 up 136 days, 49 mins, 0 users, load averages: 1.32, 1.61, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.