From: Mike Amling (nospam_at_nospam.com)
Date: Fri, 14 Oct 2005 18:06:31 GMT
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?
One application of such an array: Let d=10 (and the symbols be the
digits 0 through 9), and print such an array for n=4 onto a card. Then
every 4-digit PIN is present on the card somewhere and a user of an ATM
could, if she finds it easier, recall the location on the PIN card of
her PIN rather than the PIN itself. As long as the card remains
unmarked, the card gives no information about what the PIN is.
In particular, I wish I had some however hazy recollection of the
location on such a PIN card of the 4-digit security code of a particular
cell phone I haven't used in a long time. Doh!
2x2 is minimal for d=2, n=2.
8x1 is sufficient, and I think minimal, for d=2, n=3.