Blocker sets, orthogonal arrays and their application to combination locks

Baartmansa, Alphonse ; Sane, Sharad (2008) Blocker sets, orthogonal arrays and their application to combination locks Discrete Mathematics, 308 (13). pp. 2885-2895. ISSN 0012-365X

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1016/j.disc.2006.06.051

Abstract

Let A denote a set of order m and let X be a subset of Ak+1. Then X will be called a blocker (of Ak+1) if for any element say (a1,a2,...,ak,ak+1) of Ak+1, there is some element (x1,x2,…,xk,xk+1) of X such that xi equals ai for at least two i. The smallest size of a blocker set X will be denoted by α (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) equals 2n2 for all n. Using orthogonal arrays, we obtain precise numbers α(m,k) (and lower bounds in other cases) for a large number of values of both k and m. The case k=2 that is three coordinate places (and small m) corresponds to the usual combination lock. Supposing that we have a defective combination lock with k+1 coordinate places that would open if any two coordinates are correct, the numbers α(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) is m2 since allowing the first two coordinates to take all the possible values in A will certainly obtain a blocker set. The results in this paper essentially prove that α(m,k) is no more than about m2/k in many cases and that the upper bound cannot be improved. The paper also obtains precise values of α(m,k) whenever suitable orthogonal arrays of strength two (that is, mutually orthogonal Latin squares) exist.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Blocker Sets; Orthogonal Arrays
ID Code:68027
Deposited On:02 Nov 2011 03:12
Last Modified:02 Nov 2011 03:12

Repository Staff Only: item control page