Let D equal the number of digits for the security code. Let K equal the number of digits on the keypad.

For a binary keypad (0, 1) and a three-digit code, our set consists of (000E, 001E, 010E, 011E, 100E, 101E, 110E, 111E). Thus, we have at most $2^3 \times (3+1)$ possible keys to enter, where the plus one is for the ENTER key. Generally speaking, we'd have $K^D \times (D+1)$ possible keys to enter.

Without the ENTER key, we could keep pressing the keypad until all combinations have formed. The minimum number of keys required would be $K^D + D$.

So for a binary keypad, we'd have:

D | String | Keys (wo/ E) | Keys (w/ E) |
---|---|---|---|

1 | 01 | 2 | 4 |

2 | 00110 | 5 | 12 |

3 | 0001110100 | 10 | 32 |

4 | 0000111100101101000 | 19 | 80 |

5 | 000001111100010010101110110011010000 | 36 | 192 |

Thus, one only needs to know the string concatenations to be able to guess the right combination if no ENTER or code-stopper key is required.

**Update**: See De Bruijn Sequence and ProjectEuler #265 for a related problem.

## No comments:

Post a Comment