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 \le 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 Sands (2011), by showing that $[1,2]$ is a solution to the $n$-card problem for all $n \ge 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 \ge 2$.
@article{10_37236_2444,
author = {Justin H.C. Chan and Jonathan Jedwab},
title = {The \(n\)-card problem, stochastic matrices, and the extreme principle},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2444},
zbl = {1253.05006},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2444/}
}
TY - JOUR
AU - Justin H.C. Chan
AU - Jonathan Jedwab
TI - The \(n\)-card problem, stochastic matrices, and the extreme principle
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2444/
DO - 10.37236/2444
ID - 10_37236_2444
ER -
%0 Journal Article
%A Justin H.C. Chan
%A Jonathan Jedwab
%T The \(n\)-card problem, stochastic matrices, and the extreme principle
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2444/
%R 10.37236/2444
%F 10_37236_2444
Justin H.C. Chan; Jonathan Jedwab. The \(n\)-card problem, stochastic matrices, and the extreme principle. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2444
