7
$\begingroup$

A bored jailer tells a prisoner that if he can guess a secret number he will be set free. The rules are given that the number will not be more than three digits in length and the prisoner may guess the number as many times as necessary, as long as his guesses meet one of the following requirements each time:

  • Guess contains a digit in the secret number
  • Guess has a value less than the secret number

The prisoner is told which conditions his guesses match.

If the secret number is three digits long, which number would take the least guesses?

Which guesses would the prisoner use?

Which secret number would take the most guesses?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ I'm confused, if his guess doesnt meet the requirements what happens? You say he can guess as many times as necessary as long as his guess meets the requirements. $\endgroup$
    – Thomas Markov
    Dec 5 '19 at 19:38
  • 1
    $\begingroup$ lets say he guesses 56 for his first guess. if the number was 47 he loses. if the number is 78 he gets another guess although neither digit is in the answer however he gets another guess because it is less than the answer $\endgroup$
    – FrostedSyntax
    Dec 5 '19 at 20:04
  • 1
    $\begingroup$ No, the way you worded it, his guess must meet BOTH requirements to be able to keep guessing. $\endgroup$
    – Thomas Markov
    Dec 5 '19 at 20:06
  • 2
    $\begingroup$ the prisoner does not know how many digits. and yes Thomas you are right, i edited the wording $\endgroup$
    – FrostedSyntax
    Dec 5 '19 at 20:08
  • 1
    $\begingroup$ Can the number start with a 0? $\endgroup$
    – Jens
    Dec 5 '19 at 20:25
3
$\begingroup$

Okay, the actual strategy.

Prisoner guesses 0-9, noting which three guesses satisfy the number contained requirements. Then wolog $x<y<z$ were his three number matched guesses. Then he guesses yxz or yzx. This strategy takes at most 13 guesses depending on which ordering of x, y, and z is correct.

If the secret number is three digits long, which number would take the least guesses?

This strategy would take at most six guesses if the number contains 0, 1, and 2.

Which secret number would take the most guesses?

Any number containing three distinct values having form xy9 or 9yx would take up to 13 guesses.

Improve this answer
$\endgroup$
16
  • $\begingroup$ well, yes...but i asked which numbers would take the least and most guesses if looked at strategically. $\endgroup$
    – FrostedSyntax
    Dec 5 '19 at 20:15
  • $\begingroup$ I'm not a game theorist, but it seems to me that a method which guarantees success better fits the definition of "strategy" than a method which doesn't, especially when there are no move or time constraints. A method is not really a "strategy" unless it yields favorable outcomes. In this case, what you are calling strategy sacrifices guaranteed freedom for the novelty of your solution. $\endgroup$
    – Thomas Markov
    Dec 5 '19 at 20:18
  • 1
    $\begingroup$ There are more efficient methods that still guarantee success $\endgroup$
    – StephenTG
    Dec 5 '19 at 20:19
  • $\begingroup$ @FrostedSyntax gave it a real shot. $\endgroup$
    – Thomas Markov
    Dec 5 '19 at 20:30
  • 1
    $\begingroup$ Sorry, but 102 would only take 4 guesses. $\endgroup$
    – Jens
    Dec 5 '19 at 20:38
0
$\begingroup$

OK. If we allow denormalized values like "057", then our first guess is "210", and it takes not more than 9 guesses, and as few as 1 if the secret number was "210". It takes an average of 7.311 guesses. (An interesting result: 1/8th of the numbers take a full 9.)

If we don't allow denormalized values, then our first guess is "321", and it still takes not more than 9 guesses. It takes an average of 7.09555... guesses.

The strategy starts by observing that every guess splits the space of possibilities five ways.

  1. that we guessed the secret number.
  2. that we guessed higher than the secret number and didn't match digits, and therefore lost. We must choose our guesses to make this space empty!
  3. that we guessed lower than the secret number, and didn't match digits.
  4. that we guessed higher than the secret number, and matched digits.
  5. that we guessed lower than the secret number, and matched digits.

The secret is to make the smallest the last three as large as possible. If we could produce an equal split, we could achieve a win in seven guesses. We can't get an equal split.

The first guess of 210 or 321 is the largest number that includes all possible first digits of any smaller number, thus guaranteeing no loss, and getting good splits (1/0/343/210/446 or (1/0/294/221/384). This is the shortest possible guess.

The worst case? Any that take 9 guesses. 432 and 997 is a good examples as they take 9 with or without denormalized numbers.

I'm not going to try to show a full decision tree, since they are huge.

An ideal strategy might to a bit better than what I've cited, as my testing was done based on finding all possible guesses that got the best split, discarding those that aren't possible secret numbers if any are, and then taking the lowest.

I haven't tried the possibility that we are not told that we have guessed the secret number, and must prove it based on other evidence. Even that probably won't take more than 10 guesses.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.