Blocker sets, orthogonal arrays and their application to combination locks

Let AA denote a set of order mm and let XX be a subset of Ak+1Ak+1. Then XX will be called a blocker   (of Ak+1Ak+1) if for any element say (a1,a2,…,ak,ak+1)(a1,a2,…,ak,ak+1) of Ak+1Ak+1, there is some element (x1,x2,…,xk,xk+1)(x1,x2,…,xk,xk+1) of XX such that xixi equals aiai for at least two ii. The smallest size of a blocker set XX will be denoted by α(m,k)α(m,k)and the corresponding blocker set will be called a minimal blocker  . Honsberger (who credits Schellenberg for the result) essentially proved that α(2n,2)α(2n,2) equals 2n22n2 for all nn. Using orthogonal arrays, we obtain precise numbers α(m,k)α(m,k) (and lower bounds in other cases) for a large number of values of both kk and mm. The case k=2k=2 that is three coordinate places (and small mm) corresponds to the usual combination lock. Supposing that we have a defective combination lock with k+1k+1 coordinate places that would open if any two coordinates are correct, the numbers α(m,k)α(m,k) obtained here give the smallest number of attempts that will have to be made to ensure that the lock can be opened. It is quite obvious that a trivial upper bound for α(m,k)α(m,k) is m2m2 since allowing the first two coordinates to take all the possible values in AA will certainly obtain a blocker set. The results in this paper essentially prove that α(m,k)α(m,k) is no more than about m2/km2/k in many cases and that the upper bound cannot be improved. The paper also obtains precise values of α(m,k)α(m,k) whenever suitable orthogonal arrays of strength two (that is, mutually orthogonal Latin squares) exist.