We’ve got a spare key in a box in the backyard. The box has a modified (as explained below) Simplex style lock to allow access to the key. Given how easy Simplex locks are to crack, I worry that this one might be easier still.
The lock works like this: There are ten numbered buttons. So far as I know, the combination can be anywhere from one to ten of these, subject to two conditions: 1) in usual simplex fashion, each number can only be used once, so 1234 would be a valid combination, but 1231 would not. 2) The order of the buttons used is irrelevant. So, if the combination is 1234, then 4321, 3412, 2143, etc., will all open the lock.
Yeah, typing “10 choose 4” into Google, I also get 210.
Doesn’t seem like a terribly secure lock to me. Not only that, I would expect that the buttons used for the combination would either experience additional wear over time or leave residue finger grease on them (which a little powder would reveal) would offer more clues to the would-be lock cracker.
The combo doesn’t have to use four, it can use just one, or all ten:
Hmmm…I think the formula would use a sum of “semi-factorials” (I know there’s a real word for that, but I can’t think of it.) So the total would be:
1098765432 (ie, 10!) (if you use all 10 numbers this is how many combinations there are.)
+
1098765432 (we have this many using just 9 numbers)
+
10987654*3 (using 8 numbers.)
So we do this until we get to using just one number, and we get: 9,864,100…I think. Someone should check my math.
The problem with this answer is that you’re taking order into consideration. 10! is how many possible arrangements of 10 items there are, but the OP says that order is irrelevant, so you want the choose function (binomial coefficient). “N choose K” tells you how many k-element subsets there are in an n-element group. Hence, for a 10 digit code, there should be one possible combination (10 choose 10), since all the buttons will be pressed down, and the order in which we press them is irrelevant, not 10! combinations.
Yes, since any combination either includes, or does not include each digit, there are 2^n possible combinations. The only invalid combination is no digits.
Ah! That’s actually quite clever. Just think of it as a 10-digit binary number, subtracting 1 for “0000000000” (an invalid combo). That’s a much easier way to think about this problem.
Really it’s almost the same approach you used earlier, but rather than adding up all of the sub-cases, just subtract the one invalid case from the total possibilities.
(10 choose any number) - (10 choose zero)
When I saw the pattern of a sum of (10 choose i), a little bell went off in my head that said binomial theorem.
Credit for cleverness goes to Blaise Pascal in this particular incidence.
I’m trying to figure out from all of the posts if you guys are describing the lock I think you are describing.
Because the ones I used worked like this:
(from here)
The part that is confusing me is that the ones I used you could press “1,3” at once and then press “2”. Both 1 and 3 would go in at the same time, and then 2 in a second step. If the combo was set this way, then an attempt at pressing “1” followed by “2,3” would not work.
And point 5 in this list is kind of silly since you can’t simultaneously press multiple buttons in any order. I assume it was mentioned simply to clarify this for the sake of the math problem.
Thanks, guys. Ever since I realized that the order of buttons pushed was irrelevant, I suspected that the lock would be trivial to ‘pick’ by brute force. I just lacked the mathematical chops to prove it.
minor7flat5, what you’re describing is the classic Simplex lock. The box in my backyard is a variation on the basic concept–ten buttons instead of five; order of presses irrelevant; no meaningful ability to use multiple-button presses (while you could press {1 2} {3 4}, this would be no different than 1 2 3 4 or {1 2 3 4}, etc.).
Still not great, though. These were common around my undergraduate university, and with a team of two (one reading off possible combos, one punching them) you could attain a mean-time-to-entry of under ten minutes. If you had to do it yourself if was about a factor of two slower.
Just (voice) record the combos on computer, stick it on your iPod, and there ya go. If you look online, you can find a list of all the combinations – there’s only 1,082 on a 5-button simplex lock.
No no no. He’s not taking order into consideration by saying it’s 10987654321. That would be 10101010*10…etc.
The order doesn’t matter. It just means that the first number has 10 possibilities. The second number has 9 possibilites because the first one used one of them. The third number has 8 possibilities because the first and second ones used two of the 10. And so on down the line.
The first number could be any number. The second one could also be any number provided you do not know what any of the other numbers is. And the third number is the same. 10 possibilities. But as you start to figure out each digit the subsequent possibilities of the other digits decreases.
The order doesn’t matter. Whether it’s 10987654321 or 65432110987 it doesn’t matter. The product is the same: 3,628,800
I’m not sure what you mean. 101010 implies he can reuse number, doesn’t it?
If you have a 3-digit number, you have 3! posibilities of arranging them, or 6:
123
132
213
231
312
321
If you have a 4-digit number, you have 4! possibilties, or 12, of arranging the numbers.
Ergo, if you have a 10-digit number, there’s 10! possibilities for arranging the digits. So, when he says “if you use all 10 numbers this is how many combinations there are,” that’s correct. That’s how many ways there are to arrange 10 numbers, in other words, where sequence is important. In our problem, though, all those cominations yield the same result: all numbers pressed down. Therefore, (10 choose 10), or one.
When he says 1098*…2 for a nine-digit combination, once again, he’s taking into account order. We want (10 choose 2), or 45.
Once again, see the 3 digit possibility:
Order unimportant: 12 23 13 (3 choose 2)
Order important: 12 13 21 23 31 32 (3*2)