turkmath.org

The n-card problem is to determine the minimal intervals [u,v] such that for every stochastic matrix A of order n there is a permutation matrix P of order n (depending on A) such that tr(PA) lies 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 < 5. I shall describe a method of analysis for the n-card problem that makes repeated use of the Extreme Principle. This method answers a question posed by Sands, by showing that [1,2] is a solution to the n-card problem for all n. The method also shows that each closed interval of length n/(n-1) contained in [0,2) is a solution to the n-card problem for all n. This is joint work with Justin Chan.