My friend MF was invited to visit AF (another friend of mine).
At the entrance door to AF's place (apartment building with 36 tenants) there was a 10 digit keyboard panel.
Noticing that only 2 keys showed signs of use and assuming that the 4 digit number usually represents someone's birthday date (either MMDD or DDMM), he keyed his guess and surprised AF by arriving without using the intercom.

Given that the code number is based on birth date and the "used keys" can be correctly detected, please answer the following questions:
1. What possible couples of digits enable a "first-guess" correct solution?
2. What is the worst case (i.e. the longest list of trials) for 2 "used digits"?
3. What is the best case for 3 "used digits" (defined for different triplets)?
4. What is the worst case for the above?

DATA 31,28,31,30,31,30,31,31,30,31,30,31
DIM molen(12)
FOR i = 1 TO 12: READ molen(i): NEXT

FOR mo = 1 TO 12
 FOR da = 1 TO molen(mo)
  s$ = LTRIM$(STR$(100 * mo + da)): IF LEN(s$) < 4 THEN s$ = RIGHT$("00" + s$, 4)
  ct = 0
  FOR p = 4 TO 1 STEP -1
     IF INSTR(MID$(s$, p + 1), MID$(s$, p, 1)) = 0 THEN
       ct = ct + 1
       dig(ct) = VAL(MID$(s$, p, 1))
     END IF
  NEXT p
  IF ct = 2 THEN
   PRINT s$; " ";
   IF dig(2) < dig(1) THEN SWAP dig(2), dig(1)
   tot(2, dig(1), dig(2)) = tot(2, dig(1), dig(2)) + 1
  ELSEIF ct = 3 THEN
   IF dig(2) < dig(1) THEN SWAP dig(2), dig(1)
   IF dig(3) < dig(2) THEN SWAP dig(3), dig(2)
   IF dig(2) < dig(1) THEN SWAP dig(2), dig(1)
   tot3(dig(1), dig(2), dig(3)) = tot3(dig(1), dig(2), dig(3)) + 1
  END IF
 NEXT
NEXT

PRINT

FOR low = 0 TO 9
PRINT USING "###  "; low;
FOR high = 0 TO 9
  PRINT USING "###"; tot(2, low, high);
NEXT: PRINT
NEXT

PRINT : PRINT
FOR l1 = 0 TO 1
  PRINT l1

  FOR low = 0 TO 9
  PRINT USING "###  "; low;
  FOR high = 0 TO 9
    PRINT USING "###"; tot3(l1, low, high);
  NEXT: PRINT
  NEXT
NEXT

shows

For parts 1 and 2:

the following are the applicable codes:

0101 0110 0111 0202 0220 0222 0303 0330 0404 0505 0606 0707 0808 0909 1001 1010 1011 1101 1110 1112 1113 1114 1115 1116 1117 1118 1119 1121 1122 1211 1212 1221 1222

The following tables show how many dates exhibit the given pairing of the digit on the left of the row with the digit above the column (shown only for lower number on the left):

       0  1  2  3  4  5  6  7  8  9

  0    0  8  3  2  1  1  1  1  1  1
  1    0  0  7  1  1  1  1  1  1  1
  2    0  0  0  0  0  0  0  0  0  0
  3    0  0  0  0  0  0  0  0  0  0
  4    0  0  0  0  0  0  0  0  0  0
  5    0  0  0  0  0  0  0  0  0  0
  6    0  0  0  0  0  0  0  0  0  0
  7    0  0  0  0  0  0  0  0  0  0
  8    0  0  0  0  0  0  0  0  0  0
  9    0  0  0  0  0  0  0  0  0  0

So zero with 4 through 9, or 1 with 3 through 9 have only one possible date.

The worst case is zero and 1, with 8 possibilities.

For parts 3 and 4:

The first table below is for sets where the lowest digit is zero; the second is for sets where the lowest digit is 1. The remaining two digits are arranged as in the table above for 2-digit values, so again, lower digit is on left of the row and higher digit above the column.

 0
       0  1  2  3  4  5  6  7  8  9
 
  0    0  0  0  0  0  0  0  0  0  0
  1    0  0 21 15  9  9  9  9  9  9
  2    0  0  0  6  6  6  6  6  6  5
  3    0  0  0  0  3  3  3  3  3  3
  4    0  0  0  0  0  2  2  2  2  2
  5    0  0  0  0  0  0  2  2  2  2
  6    0  0  0  0  0  0  0  2  2  2
  7    0  0  0  0  0  0  0  0  2  2
  8    0  0  0  0  0  0  0  0  0  2
  9    0  0  0  0  0  0  0  0  0  0

 1
       0  1  2  3  4  5  6  7  8  9
 
  0    0  0  0  0  0  0  0  0  0  0
  1    0  0  0  0  0  0  0  0  0  0
  2    0  0  0  4  3  3  3  3  3  3
  3    0  0  0  0  0  0  0  0  0  0
  4    0  0  0  0  0  0  0  0  0  0
  5    0  0  0  0  0  0  0  0  0  0
  6    0  0  0  0  0  0  0  0  0  0
  7    0  0  0  0  0  0  0  0  0  0
  8    0  0  0  0  0  0  0  0  0  0
  9    0  0  0  0  0  0  0  0  0  0

 
The best cases are for 045 - 049, 056 - 059, 067 - 069, 078, 079, 089, with two possibilities each.

The worst case is 012, with 21 possible combinations.

The 5 listed for 029 does not include leap-year day, so there are actually six possibilities, but one of them has only 1/4 the probability of the others.

BTW, the 3-digit dates are:

0102 0103 0104 0105 0106 0107 0108 0109 0112 0113 0114 0115 0116 0117 0118 0119 0120 0121 0122 0130 0131 0201 0203 0204 0205 0206 0207 0208 0209 0210 0211 0212 0221 0223 0224 0225 0226 0227 0228 0301 0302 0304 0305 0306 0307 0308 0309 0310 0311 0313 0320 0322 0323 0331 0401 0402 0403 0405 0406 0407 0408 0409 0410 0411 0414 0420 0422 0424 0430 0501 0502 0503 0504 0506 0507 0508 0509 0510 0511 0515 0520 0522 0525 0530 0601 0602 0603 0604 0605 0607 0608 0609 0610 0611 0616 0620 0622 0626 0630 0701 0702 0703 0704 0705 0706 0708 0709 0710 0711 0717 0720 0722 0727 0730 0801 0802 0803 0804 0805 0806 0807 0809 0810 0811 0818 0820 0822 0828 0830 0901 0902 0903 0904 0905 0906 0907 0908 0910 0911 0919 0920 0922 0929 0930 1002 1003 1004 1005 1006 1007 1008 1009 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1030 1031 1102 1103 1104 1105 1106 1107 1108 1109 1120 1123 1124 1125 1126 1127 1128 1129 1130 1201 1202 1210 1213 1214 1215 1216 1217 1218 1219 1220 1223 1224 1225 1226 1227 1228 1229 1231

Posted by Charlie on 2013-03-01 13:11:53