The \(n\)-card problem, stochastic matrices, and the extreme principle (Q456313)

Summary: The \(n\)-card problem is to determine the minimal intervals \([u,v]\) such that for every \(n \times n\) stochastic matrix \(A\) there is an \(n \times n\) permutation matrix \(P\) (depending on \(A)\) such that tr\((PA) \in [u,v]\). This problem is closely related to classical mathematical problems from industry and management, including the linear assignment problem and the travelling salesman problem. The minimal intervals for the \(n\)-card problem are known only for \(n \leq 4\). We introduce a new method of analysis for the \(n\)-card problem that makes repeated use of the Extreme Principle. We use this method to answer a question posed by \textit{B. Sands} [``Cards, permutations, and sums'', Contrib. Discrete Math. 6, 1--19 (2011)], by showing that \([1,2]\) is a solution to the \(n\)-card problem for all \(n \geq 2\). We also show that each closed interval of length \(\frac{n}{n-1}\) contained in \([0,2)\) is a solution to the \(n\)-card problem for all \(n \geq 2\).