2
$\begingroup$

Suppose I need to guess a password of one digit. Each time I'm wrong the password increases by another digit. What's the probability that I can correctly guess the password (assuming I have unlimited amount of time and the number is all uniform)?

My approach: since the number is generated random, it doesn't matter what strategy we adopt to guess the number. So consider the following sequence of guess $1, 21, 221, 2221, 22221, ...$. The probability that the password results in $k$-th guess is then $\frac{1}{10^n}$. Thus the total probability is $\sum_n \frac{1}{10^n}$. So the probability is $0.11111111111... = \frac{1}{9}$.

Is my approach correct, and if so, is there any better solution for this. The fraction $\frac{1}{9}$ seems to suggest an easier perspective to look at this puzzle.

$\endgroup$
3
  • $\begingroup$ The probability of succeeding on the $k$th guess must account for failing at the $1$st, $2$nd, ... , $k-1$th guess. I don't think this has been taken into account. For example, if you have to find $21$, you have to first fail at $2$ : so the probability of succeeding at the second turn is not $\frac 1{100}$ but rather $\frac{9}{10} \times \frac{1}{100}$, because you need to fail the first time. Also realize another thing : let's say you call out $5$ and fail. Then you KNOW that when you add a digit , the resulting number doesn't start with $5$ (so it can't be e.g. $54$). Strategy improved. $\endgroup$ Jul 25 at 6:31
  • $\begingroup$ I don't understand your comment. If I succeed at the second turn with the guess $21$, then that means the first digit is $2$, which I guessed wrong by saying $1$, and the second digit is $1$, which I guessed right. So the probability here is $\frac{1}{100}$. Because the first digit is $2$ so that should already include the events that I guess the first one wrong $\endgroup$
    – The One
    Jul 25 at 7:03
  • $\begingroup$ If you guessed $2$ and got it wrong, then you know the number cannot be $2$, so it can be any of the others. But once a digit is added, you know that the password cannot be , say $20,21,23,27$ etc., because if it was, then the previous answer would have had to be $2$, and you would have been correct. So you do get information from wrong guesses. From wrong guesses, you know , for example what the future password cannot start with : your guess that was called wrong. $\endgroup$ Jul 25 at 7:06
5
$\begingroup$

What is the probability that you keep failing indefinitely?

Probability that you fail first time is $\cfrac{9}{10}$

Probability that you fail twice in a row? Now here I assume that the person guessing the password can keep track of what they guessed and does not choose from the one's that are obviously incorrect.

Say you guessed $2$ first time and it was wrong. Now one digit gets added. So you need to guess from $100$ numbers ($00 - 99$) but you also know it cannot be any number between $20$ and $29$.

So probability that you fail twice in a row is,

$\cfrac{9}{10} \cdot \cfrac{89}{90} = \cfrac{89}{100}$

Now for the third guess, say you guessed $2$ the first time and $18$ the second time and failed both times, you know the three digit number is not between $200 - 299$ and you also know it is not in $180 - 189$.

Probability that you fail thrice in a row is,

$\cfrac{9}{10} \cdot \cfrac{89}{90} \cdot \cfrac{889}{890} = \cfrac{889}{1000}$

You see the denominator of the third is divisible by numerator of the second, denominator of the second by the numerator of the first?

Eventually at the end of $n$ guesses, probability that you failed in all of them is

$P(F) = \cfrac{10^n - 10^{n-1} - 10^{n-2} ... - 10^0}{10^n} $

So probability that you succeed in $n$ guesses,

$P(S) = 1 - P(F) = \cfrac{10^n - 1}{9 \cdot 10^n}$

Now as $n \to \infty$, what do you get for $P(S)$?

$\endgroup$
3
  • 1
    $\begingroup$ +1, I know it's kind of "obvious" that making random guesses (with the idea of eliminating previous guesses) is the best strategy, but I've never actually seen a mathematical proof that "XYZ strategy is the best for ABC problem". I think I'll attach one when I see it here. I mean, we all kind of understand that symmetry means that any possibility is likely, but having it out there would still be nice. There must be like this "space" or set of strategies, on which we can put a distance and have like a "best-fit" criterion which works here. Very interesting, though! $\endgroup$ Jul 25 at 7:42
  • $\begingroup$ @TeresaLisbon thank you. yes for the purpose of this question, I assume guesses are random with elimination of previous guesses. It will definitely be interesting to see if there are strategies that can better random guess in this setting. $\endgroup$
    – Math Lover
    Jul 25 at 7:55
  • 1
    $\begingroup$ Yes, I do not think that there is a better strategy than random guessing with the kind of elimination you make. I will look for sources anyway and let you know, thanks for the response. $\endgroup$ Jul 25 at 7:57

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.