On a property of a three-dimensional matrix (Q2249936)

Summary: Let \(S_n\) be the symmetrical group acting on the set \(\{1,2,\dots,n\}\) and \(x, y\in S_n\). Consider the set \(W=\{(i,x(i), y(i))\;|\;1\leq i\leq n,\;|i-x(i)|>1\vee |i-y(i)|>1\vee|x(i)-y(i)|>1\}\). The main result of this paper is the following theorem. If the number of \(W\) set entries is more than \([n/3]\), then there exist entries \((i_1,x(i_1),y(i_1)), (i_2,x(i_2),y(i_2)), (i_3,x(i_3),y(i_3))\in W\) such that \(|i_1-x(i_2)|\leq 1\), \(|i_1-y(i_3)|\leq 1\), and \(|x(i_2)-y(i_3)|\leq 1\). The application of this theorem to the three-dimensional assignment problem is considered.