On a 2-dimensional search problem (Q1329699)

A search problem of G. O. H. Katona is studied. The objective of it is to obtain bounds on the number of questions needed to find an unknown element of the lattice of the pairs of integers \((i,j)\) \((1\leq i\leq n\), \(1\leq j\leq m)\). The search questions can be of type if \({\mathbf x}\leq{\mathbf a}\) for any \({\mathbf a}= (a_ 1,a_ 2)\), where \({\mathbf x}= (x_ 1,x_ 2)\leq {\mathbf a}= (a_ 1,a_ 2)\) means that \(x_ 1\leq a_ 1\) and \(x_ 2\leq a_ 2\). A worse case analysis in the adaptive case is given. For a large class of lattices an algorithm is given which finds the unknown element in less steps than the coordinate-wise search. On the other hand it is proved that for infinitely many lattices the information theoretic lower obund on the number of steps needed to find the unknown element is not tight.