I’m trying to come up with a solution to this, but can’t quite grasp it. Please help. I am sure that this is probably some sort of standard problem, but I don’t know the name of it.
Say you have a briefcase with a 4 digit combination lock. The combination could be anything from 0000 to 9999. Now, you have totally forgotten the combination to open it, but you need to get in there in a hurry… Would you be better off trying 0000, 0001, 0002, 0003… until you get it, or would you have a better chance trying a random combination.
There are 10000 different combinations, so on the first try, you have a 0.01% chance of getting it right. But under the methodical elimination method, your chance of getting it increase each subsequent try because you have decreased the possible number of combinations it could be.
Under the random method, there are 2 scenarios. If you can remember each combination you have previously tried, then your chances on each subsequent attempt are the same as if you were using the methodical elimination method. The second scenario would be if you could not remember which combinations had been tried. Then each attempt would have the same chance of success.
I imagine that if the combination were something high, like 9876, then you would be better off using one of the random methods but by how much? On average, would any method be more advantageous?
This is meaningless. It is analogous to saying that if the combination is 1176 and your first random guess happens to be 1176 you are better off using the random method.
Obviously, before you set conditions on what the actual number is, any method that eliminates repeats is better than one that doesn’t.
If you don’t have any information in advance about the combination you can’t do better than methodically trying each one in sequence.
Sure, if the combination is high you’ll take longer (on average) than with the random-no-repeats method. But this is balanced by the times where the combination is low and you take less time (on average) than random-no-repeats.
(As a generally rule of thumb, it’s hard to think about probabilities of isolated events. Restructuring the problem so that it involves repeated trials usually makes the solution more obvious.)
In theory, the two techniques are statistically equivalent.
In practice, there are two problems with the random technique: a) there is more setup time involved, b) there is accounting time involved, since you need to log your attempts to make sure you don’t duplicate effort. Therefore, the random technique is slower.
If you go with the first random method you described (choosing without replacement) there is really no difference between that and the ‘start from zero’ method. In both systems you will proceed through every number in some particular order. Imagine if, instead of choosing a new random combination from ones you haven’t tried, you were given a long randomly ordered list that had been prepared in advance. There’s no difference between this and and any other method of ordering, as long as the combo is random.
With the second random method (with replacement) you will obviously be taking a longer amount of time on average, since you will have ‘repeats’ on your list. I don’t have a probability text with me, so I can’t give you the details, but I think the distribution would approximate something like hypergeometric (so search on that for more).
All of this assumes that the lock combination was chosen truly randomly. If you account for human psychology – most people would not use a combo starting with “000” – the random method would likely give you better results. I say ‘likely’ here because I’m only assuming psychological information. In addition, I might try combinations of two digit numbers less than 31 (dates) or something like that.
The expected number of attempts you need to make before opening the briefcase (that is, the number of tries it will take on average) is (10000+1)/2=5000.5 for both the sequential and random-without-repeats methods, but it’s 10000 for the random-with-repeats method. In other words, it would take on average twice as long to open the briefcase by guessing numbers randomly (without keeping track of what you’ve already tried) than it would if you just tried the combinations in order.
And that’s the average-case scenario. The worst-case scenario is, well, worse.
Just wanted to point out that in general, it’s usually possible to open a 3-number combo briefcase in about 15 minutes using some sort of ordering (random or no).
If we assume my, uh, purely hypothetical, numbers are accurate, this is one combo every 2 seconds. The average amount of time to open a 4-number briefcase would be 10 times that, or about 2 1/2 to 3 hours.
This has no effect on the theoretical answer, but at the risk of stating the obvious, I’ll point out that starting at 0000 and increasing until you get to 9999 is not the only methodical way of trying all combinations. If you suspected for some reason that the combination was a high number, you could start with 9999 and work your way down to 0000. Or start with any (perhaps randomly determined) combination, go up from there until you hit 9999, then “wrap around” to 0000 and keep going.
I have no idea whether this is mathematically valid, but I always used a different system. I would break up the set into smaller pieces, and randomize those. That is, I would take the 10000 possible positions and break them up into, say, 500s, so I would try 0000 through 0500 in order, then switch to 1000 through 1500, then 2000 through 2500, etc. You could even split the 10000 into smaller pieces, say 100s. I figured spreading it out would increase my chances, but I could have been wrong.
How did I develop this system? Lets just say I enjoyed cracking combo locks as a kid. Either that, or I would forget the combo of my own lock. I can remember hours of <click><chk-chk><click><chk-chk>…
If the true combination is some number x, then the methodical approach will get the correct combination in exactly x+1 attempts. I.e., if the combination is 0000 you will get it on the first try; if it is 0100 you will get it on the 101st try.
The random method will take anywhere between 1 and 10000 tries, for an average of 5000.5 tries. That’s if you never try the same combination twice.
If you don’t remember what combinations you’ve already tried, then there’s no guarantee that you will ever get the correct combination in a finite number of steps. There is about a 50% probability that you will get the correct combination in 7000 attempts. I arrived at that number by trying out different powers of 0.9999 in my calculator (0.9999 is the probablility that a given guess will be wrong).
So, the counting method (0000,0001,0002, etc) is best if x happens to be <= 5000
If x is greater than 5000 then the random method (with memory) is best.
The random method without memory is worst.
…forgot to mention that since you don’t know anything about x beforehand (presumably) it doesn’t matter whether you use the counting method or the random method with memory. Any method that hits each of the possibilities once and only once will be equivalent.
Mathematicaly that is true but in real life the odds of having a combination made of non-repeated numbers (assuming a person chose it) is greater than a combination with repetition.
So a method that begins by exhausting x,y,z,w is superior to x,x,x,y (x=!y=!z=!w of course).
I’m assuming the average person would feel more “random” with different terms of the combination (and not trying to play mind games with intruders :)). No?
And something else occured to me, again IRL scenario: it would be faster to complete a sequential method than a random one on rolling combination locks.
This is outside the scope of the OP because it is on a practical and not theoretical level but it is answered anyway.
This is the answer I was thinking - but I wasn’t sure. My confusion is that even if the combination were above 5000 (or above first guess + 5000 if you did not start at 0000), the random guess with elimination method still might not be preferable because you could conceivably take all 10000 times to get it right, whereas you are almost guaranteed to hit it before that with the methodical elimination.
You are almost guaranteed to hit it before 10000 with the random elimination method too. This will happen unless it happens to be the 10000th number in your random sequence. The probability of finding the number in less than 10000 guesses is 9999/10000 for both methods.