How many PINs can you make with x digits?

You want to access a particular smartphone which has a 4-digit numeric pin, entered by tapping the screen. One day you see the owner wipe the screen, unlock the device, and then get distracted and walk off. You rush over, grab the phone but alas it has auto-locked again. The screen is clean except for smudge marks over the place where the 7 and the 9 appear on the screen. What is the maximum number of PINs you must test to break into the phone (and what formula can be applied for x smudge marks)?

Background: I was reading a blog post about the new "picture sign-in technique for Windows 8" which is to replace passwords, and the author compares the ease of cracking picture sign-ins to the ease of cracking standard smartphone PINs by interpreting smudge-marks on the screen (in a worst-case scenario like that detailed above). He states that the hardest case is a PIN of 4 unique digits:

“A PIN will leave a smudge in a known location for each digit used in the code. If there are n digits in the PIN, and all digits are unique (the hardest to deduce case), there will be n! possible ways of ordering the PIN. For a typical 4-digit PIN, this is 24 different combinations.”

I believe that he is incorrect; 4 unique digits is not the hardest to deduce case. I think that 3 smudges would allow 52 PINs (I've written this up in a blog post: A Shorter PIN Might Be More Secure against Smudge Attack). Then I started wondering whether 2 smudges would produce more or less permutations, but I’m not sure of what formula could be used and I refuse to count them manually on principal. Another interesting question would be the ideal amount of unique digits in the case of the PIN length being unknown to the attacker.

• Have you written down all the combinations you can think of for a 4-digit PIN using only 7's and 9's? – Joshua Shane Liberman Dec 26 '11 at 14:06
• You have miscounted the case you have stated. Two ways to see it. First, for every permutation of 1,2,3,4 you can replace the 4 with any of 1,2,3 to get a three smudge number - 24 x 3 = 72. But because a pair of the digits are equal you have to divide by 2 to get 36. Another way is to see that you can place a pair of '1's in six ways, and the remaining 2 and 3 in two ways - 12 ways with a pair of '1's - and of course it could have been '2's or '3's - multiply by 3 to give you 36. – Mark Bennet Dec 26 '11 at 14:11
• Hint following Joshua - first compute the case where you don't have to use both numbers, then subtract the exceptional cases. – Mark Bennet Dec 26 '11 at 14:12
• @Joshua no because I thought that if I did that I'd probably not bother trying to derive the formula anymore (I know, you're going to say it helps to get the formula). – Fletch Dec 26 '11 at 15:58
• @MarkBennet yes you do appear to have a point about the miscalculation. – Fletch Dec 26 '11 at 16:00

If you know that the pin is made up of only $x=2$ smudge marks, and it is a $n=4$ digit pin, the maximum number of combinations you will need to try is $x^n=2^4=16$, and the average number of pins you will need to try is $x^n/2=8$. This can be generalized for all $x,n\in\mathbb{N}$.