Keypads with paint on the buttons

Near my home there is a door that is opened by a keypad. I know that it uses a four-digit code, where the order matters, but I don’t know what the code is.

An example of a keypad

When I walked past it the other day I noticed that there were blue fingerprints over three of the numbers on the keypad, but I did not look very closely and therefore there may have been four. If there were only three numbers with fingerprints on them then I would infer that one of the numbers in the code was repeated.

I wondered this: If I wanted to guess the code as quickly as possible would I prefer that there were three digits or four digits with paint on them?

Intuitively, most people (at least in my informal survey) seemed to expect that it is more constrained when there are only three digits, and so there are fewer combinations. After all, if there was only one blob of paint, so all the digits were the same, then there would be only one possible combination, so you may expect that each digit adds more freedom and thus more combinations.

In fact, this is not the case, and you would be better placed to guess the code if you knew it had four different digits.

The number of combinations to try if you know there are four different digits is of course .  If instead it is known there are only three different digits in the code then one of them is repeated. To calculate the number fo combinations, imagine choosing the two positions in the 4-digit code that are the same digit – there are 6 (i.e. ⁴C₂) ways to do this – and then choose which digit is the one which is repeated – there are 3 to choose from. The remaining 2 digits can be arranged in 2 ways – therefore there are  ways of doing it – 50% more!

I thought this was somewhat surprising.

---

In general, suppose the painted key-pad buttons are and the lock takes an M digit code. Of course, .

I think it is easier at this point to reason if we forget about locks and talk about functions instead. A function  is equivalent to a possible code if it is surjective. The code it represents is . As f is surjective every painted digit appears at least once, as is required.

We can therefore restate the problem as counting the number of surjective functions from {1,2,…,M} to {1,2,…,N}.

It’s easy to find out the number of functions if we drop the ‘surjective’ requirement – it is N_M. This number includes non-surjective functions – where the image of the function is some proper subset of {1,2,…,N} – as well. An inclusion-exclusion argument can be used to calculate the number of surjections.

In particular, define c_ito be the number of functions f from {1,2,…,M} to {1,2,…,N} such that at least i of elements of {1,2,…,N} are missing from the image of f (i.e. the image of f is at most N-i).C_i is then easy to calculate – choose the i elements to exclude (there are ^NC_i of them) and then assign to each f(j) one of the possible remaining N-i values. Repeat that for all M function inputs and hence:

Then, by inclusion-exclusion, the number of surjective functions is:

And hence the number of surjections, and hence the number of possible lock codes of length M using N different digits, each at least once, is:

This is related to Stirling Numbers of the Second Kind.

---

Not all keypads use four-digit codes. Looking online, most digital keypad locks can use between 1 and 12 digit codes. The following chart shows the approximate number of combinations that are possible if the length of the code is known (the number on the left-hand side) and the number of painted digits is known (the number on the top):

(Here a million is 10⁶ and a billion is 10⁹)

In reality, you may not know the number of digits in the code. Here is the number of combinations that must be tried if you know an upper-bound to the number of digits in the code:

---

A few additional thoughts:

• Many digital keypads also require a card to be presented and the code is associated with the particular card (i.e. is a PIN). Then you will need access to the card too.
• Most mechanical keypads, disappointingly, don’t actually require the digits to be entered in any particular order.
• There exist keypads that randomise the digits every time they are used. In addition, they can use special screens that can only be seen when looking straight at them.
• You may be tempted to think that the repeated digit, if there was one, might have more paint on it. However, it actually turns out that the first button pressed deposited much more paint on it than the others. By way of an example, if you are looking for a four-digit code and there are three paint splodges, then by identifying the first digit you reduce the 36 combinations to 12 (not 6, as the first digit may have also been the repeated digit).