Blocker sets, orthogonal arrays and their application to combination locks (Q924978)

Let \(|A|= m\) and let \(X\subseteq A^{k+1}\). \(X\) is called a blocker of \(A^{k+1}\) if any \((k+1)\)-tuple agrees in at least two coordinates with a \((k+1)\)-tuple from \(X\). Denote by \(\alpha(m, k)\) the smallest size of such a blocker set \(X\). Clearly \(\alpha(m, k)\leq m^2\). Let \(m= nk+ r\) where \(n\geq k\geq 2\) and \(0\leq r< k\). The authors show \(\alpha(m, k)\geq (k- r)n^2+ r(n+ 1)^2\), with equality holding precisely when there exists an orthogonal array of strength 2, degree \(k+ 1\), on n symbols, and also on \(n+ 1\) symbols if \(r> 0\). If \(n\) is a prime power then, for example, \(\alpha(nk, k)= kn^2\) since an orthogonal array \(\text{OA}(n+ 1, n)\) exists.