This curious fact actually ocurred to me yesterday. It never happened before.
To grant access to the operations provided by the ATM (Automatic Teller Machine) of my bank, I have to type (touching the screen) the password of my magnetic card.
The screen which appears to me shows five "buttons", each one of them labeled with two digits, from 0 to 9. For example, in the first there are the numbers 02, in the second, 37, in the third, 45, in the fourth, 19 and in the fifth, 68. So, if my password, that consists of 6 digits, not necessarily different, is 123456, I touch, in order, the fourth button (1), the first (2), the second (3), the third (4), again the third (5) and the fifth (6).
The numbers that appear in each button change daily, and yesterday I noticed that to enter my password, I touched only two buttons. To clarify, with the configuration above, if my password were "357457", I would have touched the second button, the third, the second, the third, again the third, and the second.
What is the probability that this occurs, that is, that I have to touch only (and exactly) two buttons to enter my password, if it is made of a) 2 different digits; b) 3 different digits; c) 4 different digits?
There are two basic ways of considering the probability: considering all 10! = 3,628,800 ways of filling each of 10 positions (1st number on first button, 2nd number on first button, 1st number on second button, etc.) or considering only the 945 possibilities in a standard form, such as the lower number being first on any given button, and the buttons are in ascending order of their lower number.
The two probabilities are equal, as each of the 945 possibilities is multiplied by the same 3840 rearrangements that have the same probability (2^5 ways of flipping or not flipping positions within each button multiplied by the 5! ways of rearranging the buttons).
The first of these ways is clearer for the analytic solution, while the smaller number of cases is more efficient for the computer solution.
Analytic solution:
There are 10 positions to be filled with numbers.
For the twonumber case, consider the two numbers to be 0 and 1. The 0 can be considered to be in any position. The probability that the 1 will be in the other position on the same button (therefore requiring only one button repeatedly pressed) is 1/9. The probability that the 1 is on another button is 8/9 as there are eight equally likely places for the 1. That 8/9 is the probability that there will be two buttons to press in the case of a password with only two different digits.
For the threenumber case, consider the three numbers to be 0, 1 and 2. Again, the 1 has 1/9 probability of being on the same button as the 0, forcing the 2 to be on a second key, contributing, therefore, 1/9 to the overall probability we seek. In the 8/9 likelihood that the 0 and 1 are on separate buttons, in order to use only two buttons altogether, we need to satisfy that the 2 is on one of those two buttons. This has 2/8 probability. The overall probability for a threedigit password is then 1/9 + 8/9 * 2/8 = 3/9 = 1/3.
For a password with four different digits, take them to be 0, 1, 2 and 3. Again the 1 has 1/9 probability of being on the same button as the 0. If that's the case, the 2 has to be on the same button as the 3. By similar reasoning, that probability is 1/7 as there are seven positions left for the 3 after the 2 has been placed. On the other hand, if the 1 is on a different button from the 0, with its 8/9 probability, the 2 and the 3 must be on the same two buttons as determined by the 0 and 1. The probability that the 2 is on one of these two buttons is 2/8 = 1/4, and then the probability that the 3 is on the remaining one is 1/7. So the overall probability in the 4differentdigit case is 1/9 * 1/7 + 8/9 * 1/4 * 1/7 = 1/21
Computer solution:
The 945 cases are obtained by assuming 0 is the first number on the first button; the second number on that button is any of the remaining digits; the first number on the second button is the lowest number not yet used; the second number on the second button is any of the remaining seven digits; etc. The first number on any button is the lowest number still available, and the second number on each button is any of the digits not yet used.
As the computer is doing the calculations, it might as well compute all the probabilities rather than just those for exactly 2 buttons used.
DECLARE FUNCTION gcd! (x!, y!)
DIM howMany(10, 5) ' num diff digs, ct of num buttons reqd.
taken(0) = 1
ch(1, 1) = 0
FOR ch12 = 1 TO 9
ch(1, 2) = ch12
taken(ch12) = 1
FOR ch21 = 1 TO 9
IF taken(ch21) = 0 THEN
ch(2, 1) = ch21
taken(ch21) = 1
EXIT FOR
END IF
NEXT ch21
FOR ch22 = 1 TO 9
IF taken(ch22) = 0 THEN
ch(2, 2) = ch22
taken(ch22) = 1
FOR ch31 = 1 TO 9
IF taken(ch31) = 0 THEN
ch(3, 1) = ch31
taken(ch31) = 1
EXIT FOR
END IF
NEXT ch31
FOR ch32 = 1 TO 9
IF taken(ch32) = 0 THEN
ch(3, 2) = ch32
taken(ch32) = 1
FOR ch41 = 1 TO 9
IF taken(ch41) = 0 THEN
ch(4, 1) = ch41
taken(ch41) = 1
EXIT FOR
END IF
NEXT ch41
FOR ch42 = 1 TO 9
IF taken(ch42) = 0 THEN
ch(4, 2) = ch42
taken(ch42) = 1
FOR ch51 = 1 TO 9
IF taken(ch51) = 0 THEN
ch(5, 1) = ch51
taken(ch51) = 1
EXIT FOR
END IF
NEXT ch51
FOR ch52 = 1 TO 9
IF taken(ch52) = 0 THEN
ch(5, 2) = ch52
taken(ch52) = 1
ct = ct + 1
REDIM ctReq(10)
FOR diffDig = 1 TO 10
FOR btn = 1 TO 5
IF ch(btn, 1) < diffDig OR ch(btn, 2) < diffDig THEN
ctReq(diffDig) = ctReq(diffDig) + 1
END IF
NEXT
NEXT
FOR diffDig = 1 TO 10
howMany(diffDig, ctReq(diffDig)) = howMany(diffDig, ctReq(diffDig)) + 1
NEXT diffDig
taken(ch52) = 0
END IF
NEXT ch52
taken(ch51) = 0
taken(ch42) = 0
END IF
NEXT ch42
taken(ch41) = 0
taken(ch32) = 0
END IF
NEXT ch32
taken(ch31) = 0
taken(ch22) = 0
END IF
NEXT ch22
taken(ch21) = 0
taken(ch12) = 0
NEXT ch12
CLS
PRINT ct
FOR btnCt = 1 TO 5
LOCATE 1, btnCt * 10: PRINT btnCt;
NEXT
FOR diffDig = 1 TO 10
LOCATE diffDig + 2, 1: PRINT USING "##"; diffDig;
FOR btnCt = 1 TO 5
LOCATE diffDig + 2, btnCt * 10
g = gcd(howMany(diffDig, btnCt), ct)
PRINT STR$(howMany(diffDig, btnCt) / g);
IF howMany(diffDig, btnCt) > 0 THEN PRINT "/"; LTRIM$(STR$(ct / g));
NEXT
NEXT
END
FUNCTION gcd (x, y)
IF x = 0 OR y = 0 THEN gcd = 1: EXIT FUNCTION
d = x: r = y
IF r > d THEN SWAP d, r
DO
q = INT(d / r)
rm = d  q * r
d = r
r = rm
LOOP UNTIL r = 0
gcd = d
END FUNCTION
The output:
945 1 2 3 4 5
1 1/1 0 0 0 0
2 1/9 8/9 0 0 0
3 0 1/3 2/3 0 0
4 0 1/21 4/7 8/21 0
5 0 0 5/21 40/63 8/63
6 0 0 1/21 4/7 8/21
7 0 0 0 1/3 2/3
8 0 0 0 1/9 8/9
9 0 0 0 0 1/1
10 0 0 0 0 1/1
confirms that there are 945 cases counted and shows a matrix for the probabilities of using any given number of buttons, assuming any number of different digits in the password. The probabilities for the 2 column (two buttons required) agree with the analytically derived solution, confirming that it doesn't matter if you consider all 10! cases, with individual positions counting, or just the 945 archetypal cases. As expected, with only one password digit, it's certain only one button will be required and with nine or ten digits in the password it's certain all five buttons will be needed.

Posted by Charlie
on 20080811 14:24:17 