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 0-2, in the second, 3-7, in the third, 4-5, in the fourth, 1-9 and in the fifth, 6-8. 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 two-number 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 three-number 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 three-digit 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 4-different-digit 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 2008-08-11 14:24:17