Re: PIN card

Mike Amling wrote:

> Let's say we have an alphabet of d distinct symbols. What's the
> smallest (area) rectangular array of such symbols such that every
> n-symbol sequence of such symbols is present in the array somewhere if
> we allow reading sequences in straight lines in any of the 8 directions
> N, S, E, W, NW, NE, SW, SE?

Well, if you want the array to include every 4-digit PIN composed
of the digits 0 through 9, then it must contain 1000 PINs that
begin with, say, 7. Since each 7 in the array can be the first
digit of at most 8 PINs (taking off in the 8 allowed directions),
there must be at least 1000/8 = 125 7's in the array. And since
the same reasoning applies to the other 9 digits, there must be
at least 1250 digits in the array. More, actually, because the
digits near the edges can't start PINs in all 8 directions.

Just thinking of reading my PIN off a wallet card with a 40x30
array of digits gives me eyestrain.

Here are some results of a slapped-together Python program to
exhaustively search some small cases. Unfortunately, these
cases appear to be dominated by "edge effects" that probably
won't be nearly so important in the 40x30 case.

# digits pin length table # pins
-------- ---------- -------- ------
     2 2 2x2 4

     2 3 3x3 7
     2 3 3x4 8

     2 4 4x4 15
     2 4 3x5 12
     2 4 2x7 14
     2 4 2x8 16
     2 4 1x13 15
     2 4 1x14 16

     3 2 2x3 9
     3 2 1x6 8
     3 2 1x7 9

     3 3 3x4 22
     3 3 3x3 14
     3 3 2x4 8
     3 3 1x9 14

-- 
Peter Pearson
To get my email address, substitute:
nowhere -> spamcop, invalid -> net
[plaintext with, say, 7. Since each 7 in the array can be the first]