[Scilab-users] Combinatorics

Fri Apr 15 19:14:32 CEST 2022

Hi Mikhail and Scilabers

Thank you Mikhail for the equation with factorials, the URL to 
Wikipedia, and confirming my findings are OK (I really wasn't sure).
Although the specifics of my case (with codes on a lock) seems very 
constrained and 'special' - I suppose it is common after all.
It is interesting to see the math is quite simple.
It is also interesting to see the 'distribution' of combinations:

Buttons pushed 	0 	1 	2 	3 	4 	5 	6 	7 	8 	9 	10 	Sum =
Combinations 	1 	10 	45 	120 	210 	252 	210 	120 	45 	10 	1 	1024

It is not that 'safe' of a lock because someone can decode it within an 
hour or so. If you take e.g. 5 seconds for trying each combo, we're 
talking about 1,4 hours to try all of them and maybe you hit jackpot 
somewhere in the middle.

It is not advisable to choose 0 or 1 buttons for the code. Coding 5 
random numbers to be pushed on the lock will give the highest number of 
combinations, but 4-6 buttons gives a suitable range of codes, 7 could 
also be OK. Although more buttons pushed gives fewer combinations, it's 
unlikely that e.g. a thief will start with a high number of buttons 
pushed (pure psychology).

 From a decoding point of view, the most interesting part of the lock is 
that it isn't as simple as decoding a combination lock with 3 dials 
where you can easily keep track of how far you are. It becomes 
complicated and one kinda needs a look-up table to try all the 
combinations and it requires more concentration to go through all the 
combinations.

Cheers,
Claus

On 15-04-2022 17:59, Mikhail Urusov wrote:
> Dear Claus,
>
> Just in case you have not got an answer yet:
>
> > I can 'invent' a calculation, which could be : =10*9*8/(3*2*1) = 120 
> ... if this indeed shows the internal workings, I'd like to know why. 
> Sorry my combinatorics is so bad ... I
>
> This is right. In general, the formula for the number of 
> k-combinations of n elements is
> n! / ( k! (n-k)! ).
> Alternatively, you can write this as
> n*(n-1)*....*(n-k+1) / (k!).
> (This is the way you have written it above for n = 10 and k = 3.)
> The explanation in general is quite similar to this case:
>
> > Two buttons pushed. There's 10 * 9 / 2 = 45 combinations. Each 
> button can only be pushed once, so once you've selected the first 
> button, there's only 9 left, but also we divide by two because the 
> combination are doubled, I mean for example the combination 1-2 = 2-1 
> ... the lock doesn't know the difference. If you spread out the 
> possibilities in a 2D plane, it's like ignoring the diagonal (like 
> pushing the same button twice) and also we either ignore the upper or 
> lower triangle. Makes sense?
>
> For example, for n=10 and k=4:
> If you consider "arrangements", i.e., the combinations, where the 
> order matters (e.g., 1-2-5-7 and 2-7-5-1 are different), then you have 
> 10*9*8*7 such arrangements (for the first button you have 10 variants, 
> for the second one 9 variants, etc), but each "combination" (that is, 
> where the order does not matter) is counted 4! (=1*2*3*4) times 
> (number of permutations of 4 elements), so you need to divide: 
> (10*9*8*7)/(4!).
> For more information, see https://en.wikipedia.org/wiki/Combination
>
> Best regards,
> Mikhail
>
>
> Am Do., 14. Apr. 2022 um 13:51 Uhr schrieb Claus Futtrup 
> <cfuttrup at gmail.com>:
>
>     Dear Scilabers
>
>     I hope you can help me out. My combinatorics is a bit rusty.
>
>     So, the spouse has purchased a lock and I wondered how many
>     combinations are available?
>
>     The lock has 10 push buttons, they are numbered 1-2-3-4-5-6-7-8-9-0.
>
>     From a programming point of view, any of the numbers can be set on
>     or off, meaning there are 2^10 = 1024 combinations, as far as I
>     can see.
>
>     I wonder how they are distributed, and how many of the numbers I
>     should activate in the lock to maximize the number of combinations?
>
>     Let's see, we have:
>
>     None (none of the buttons are activated), there's exactly 1
>     combination for this situation. The lock is delivered from the
>     manufacturer in this state.
>
>     All (all of the buttons are activated), there's exactly 1
>     combination for this situation as well (no variability).
>
>     One button pushed. There's obviously 10 possible combinations
>     (push any one of the 10 buttons).
>
>     Two buttons pushed. There's 10 * 9 / 2 = 45 combinations. Each
>     button can only be pushed once, so once you've selected the first
>     button, there's only 9 left, but also we divide by two because the
>     combination are doubled, I mean for example the combination 1-2 =
>     2-1 ... the lock doesn't know the difference. If you spread out
>     the possibilities in a 2D plane, it's like ignoring the diagonal
>     (like pushing the same button twice) and also we either ignore the
>     upper or lower triangle. Makes sense?
>
>     Here starts my trouble. Three buttons pushed. Instead of looking
>     at a 2D plane, I guess you spread out in 3D. The diagonal line is
>     more than that - we have several planes where two of the three
>     numbers are the same (and which are not allowed).
>
>     To help myself out, I've tried to write all combinations where one
>     of the push buttons is number 1. We select all combinations with
>     the second button being either 2-3-4 and so on, and how many
>     combinations do we then have for the third option? See table below:
>
>     1-2-x 	8
>     1-3-x 	7
>     1-4-x 	6
>     1-5-x 	5
>     1-6-x 	4
>     1-7-x 	3
>     1-8-x 	2
>     1-9-0 	1
>
>     	36
>
>     We can then do the same for the first button = number 2, and we
>     get : 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 combinations and so on. We get:
>
>     1-x-y 	36
>     2-x-y 	28
>     3-x-y 	21
>     4-x-y 	15
>     5-x-y 	10
>     6-x-y 	6
>     7-x-y 	3
>     8-9-0 	1
>
>     	120
>
>     OK, so that was with three buttons pushed. It's always good to
>     know the answer (if it's correct :-/ I hope it is), but it's a
>     tedious process and I was wondering if you could point me to an
>     easy calculation instead? ... Ideally something that expands to 4
>     and 5 buttons.
>
>     I can 'invent' a calculation, which could be : =10*9*8/(3*2*1) =
>     120 ... if this indeed shows the internal workings, I'd like to
>     know why. Sorry my combinatorics is so bad ... I haven't played in
>     this field for a while.
>
>     Best regards,
>
>     Claus
>
>     _______________________________________________
>     users mailing list
>     users at lists.scilab.org
>     http://lists.scilab.org/mailman/listinfo/users
>
>
> _______________________________________________
> users mailing list
> users at lists.scilab.org
> http://lists.scilab.org/mailman/listinfo/users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20220415/d6cb5841/attachment.htm>