3
$\begingroup$

You broke into John Doe's house and found the safe. It has a combination lock with 4 dials ranging from 0 to 9 each. Unfortunately it's a good safe, which doesn't click when one or more digits are correct. Luckily the owner seems to be quite forgetful – as one can see from the following sheet of paper attached to a side wall: Key recovery

  • You have no idea what newspaper article is referred to. Also there is no clue where to find it. Searching through the whole house would take way too much time.
  • The same for the VHS recorder manual: No idea where it could be, nor what page 9 is about.
  • Jane must be John's wife, but you don't know their parking spots. You only saw that all 20 parking spots belonging to this appartment are in a row and are marked with numberplates. They are rented to the residents of the appartment probably in random order.
  • You don't know the birthday of any of these persons.

With the knowledge available to you, which 4-digit key is most likely to open the safe?

$\endgroup$
  • 1
    $\begingroup$ Births are not evenly distributed into months, and letters of the alphabet are also not distributed evenly in words. Are you asking us to estimate the distribution or make the (unrealistic) assumption that, e.g., the letter in the VHS manual is equally likely to be "e" or "z"? $\endgroup$ – ffao Nov 1 '17 at 20:39
  • $\begingroup$ @ffao The question is about using as much information available to you to find the key with the highest probability. This information includes the fact that some letters are more frequent than others as well as different months having different lengths. $\endgroup$ – A. P. Nov 1 '17 at 20:46
4
$\begingroup$

There's a significant amount of intuiting you can do to reduce each of A, B, C, and D, but given the fact that the soft answers give over 56 thousand possible answers that map into less than 10 thousand, the number theory of the problem naturally lends itself to a lot of collision, complicating the probabilities. Thus, a brute force answer lends itself well to this.

Brute force answer:

7101 with 54 possible combinations of a,b,c, and d mapping to it. Not taking into account any of the "soft" figures like birthdays or letter frequencies.

All in all:

This gives you a 1 in 1040 chance of opening the safe, which is much improved over 1 in 9999.

Methodology:

A has a range of 1-9 assuming people don't start numbers with 0. B has an obvious range of 1-26. C has a range of 1-20 with a maximum probability of being 1. D has an obvious range of 1-12. From there, you can brute force all 56160 possibilities in less than a second using python.

Possible improvements:

If after multiplying the soft probabilities together you get a better ratio than 1/1040, you're better off with the soft answer. Otherwise, your best bet is to use the brute force answer.

Soft answer:

5203 which gives you a .1156% chance of opening the safe

A

Thanks to @kayzeroshort for this one. According to Benford's Law, 1 is the most likely with a probability of about 30%.

B

E is the most common letter in non-technical English with a probability of 11.16%, which might possibly be shifted by the fact that it's a VCR manual.

C

The probability of seperation is highest for 1 occurring 38 of the 190 times, giving it a probability of .2

D

The least birthed month is February with about a .89 probability below the median. Combined with a birthday paradox calculation that nobody was born in February (probability .4189), this gives D as 2 with a chance of 1/.89 * .4189 = .46644

Then you just math the rest.

So your chances in all are:

.3 * .1116 * .2 * .46644 = ~.00321 or a .3121% chance of it working. It's slightly better than brute force assuming all assumptions hold up. We made assumptions that the VCR technical manual was a reasonable sample of modern English (and that it was in English in the first place), and that all of John's friends were American and were born in America fairly recently.

Additional notes

Because A, B, C, and D mix to form the 4 digits, doing a straight multiplication to get probabilities is a little disingenuous. Additionally, 5203 can only be made in 5 combinations of A, B, C, and D, compared to 54 from 7101 from the brute force.

$\endgroup$
  • 1
    $\begingroup$ You can use Benford's law to get a better estimate for A (most likely 1 with prob = ~0.3): en.wikipedia.org/wiki/Benford%27s_law $\endgroup$ – kayzeroshort Nov 1 '17 at 22:33
  • $\begingroup$ +1 Nice answer! I agree with you on A, B and C, but I don't understand how you get such a high probability for D=2. Also you mention, that the brute force method so far only counts the possibilites, but does not take into account the individual probabilities. If you resolve these two issues, I'll accept the answer. $\endgroup$ – A. P. Nov 2 '17 at 6:54
1
$\begingroup$

After 2 months without John Kossa editing his answer on this question there is still no complete solution. So I decided to post an answer to this question myself. It is also very unlikely that somebody takes the effort to put his own answer, now that John Kossa already solved the puzzle halfway.

So, what's the most likely key?
Therefore, take a look at the reconstruction variables $a$, $b$, $c$ and $d$:

$a$:

One might think all digits are equally likely, but this is not the case for the first digit of a number. Benford's law describes that the probablity distribution for $a$ is $$P(a) = \text{log}_{10} \left( \frac{a+1}{a} \right) \text{.}$$ With this $a$ is most likely to be $1$ with a probablilty of $30.1 \, \%$. This is the probability distribution for $a$:

$b$:

Letters are also not equally distributed. As this is the 21st letter on a page of a (probably) English manual we cannot use the distribution of first letters of a word, but the general probability distribution. This distribution looks like:

$c$:

For the first of the two parking spots there are $20$ possibilities, for the second one $19$. This gives $380$ possible settings. In $38$ settings the distance between the parking spots is $1$. For a distance of $c=2$ there are only $36$ possibilities left. For each further increase of $c$ the number of possibilities drops by $2$. This gives the following probability distribution:

$d$:

This one seems to be less obvious than I thought. We may assume that the piece of paper with the instructions is meant to give a clear answer for John Doe (who knows the birth dates of these 11 people). The answer is only unique if the 11 people are born in 11 different months, so that $d$ gets its value from the remaining month. How this looks in terms of probability was answered in this question. The probability distribution is $$P(d) = \frac{1}{m_d \left( \sum\limits_{i=1}^{12} \frac{1}{m_i} \right)}$$ where $m_i$ is the length of the $i$th month. As February is the shortest month, the probability that none of the 11 persons is born in this month is maximal with $P(2) = 8.97 \, \%$.

If we now take the most likely values of

$a=1$, $b=5$, $c=1$ and $d=2$, we get $\left( 7000 \cdot 5 + 100 \cdot 2^{1+1} + \left\lfloor \frac{5 \cdot 1 + 2^2}{1^{3-5}} \right\rfloor + 2 \right) \text{mod} 10000$ $= \left( 35000 + 400 + 9 + 2 \right) \text{mod} 10000$ $= 5411$ with a probability of $0.034 \, \%$, which is at least better than just guessing.

But wait...

... there are in total $53352$ possible $(a, b, c, d)$ tuples which map onto $10000$ possible keys. This means it makes sense to make a histogram of all possible keys. But instead of just counting the number of possible tuples that map onto the same key, we weight the tuples with their individual probabilities.

The biggest peak is for a key of $7101$ with a probability of $0.154 \, \%$, which is twice as likely as the previous "solution" $5411$ ($0.081 \, \%$).

To understand this we take a look at a possible $(a, b, c, d)$ tuple leading to a key of $7101$, namely $(1, 1, 1, 1)$. This deviates from the most likely values of $b$ and $d$, but leads to many tuples mapping to the same key: With $d=1$ the term $100 \cdot d^{a+1}$ becomes independent of $a$, hence the second digit of the key is the same for (almost) all values of $a$.
The reason for $b=1$ is more subtle. If $b > 3$ the exponent in the denominator of the term $\left\lfloor \frac{5c + 2^d}{a^{3-b}} \right\rfloor$ becomes negative, hence the term will get big easily, which means that it will map the $(a, b, c, d)$ tuples onto many different keys. The smaller $b$ is the smaller this term will be. For the smallest value of $b = 1$ the term will result in $0$ for most values of $a$, $c$, $d$.

$\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.