# The $n$-Card Problem, Stochastic Matrices, and the Extreme Principle

• Justin H.C. Chan
• Jonathan Jedwab
Keywords: Stochastic matrix, Permutation matrix, Transversal sum, Trace, Extreme Principle, $n$-card problem

### Abstract

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$.
Published
2012-06-28
Article Number
P53
{"ft_lang_label":"__label__en","ft_lang_prob":0.88966805,"math_prob":0.99837667,"size":1095,"snap":"2021-43-2021-49","text_gpt3_token_len":289,"char_repetition_ratio":0.15857013,"word_repetition_ratio":0.0952381,"special_character_ratio":0.2630137,"punctuation_ratio":0.0952381,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997156,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-12-01T14:44:31Z\",\"WARC-Record-ID\":\"<urn:uuid:59a43202-2547-4d0f-9de4-2010446cd56b>\",\"Content-Length\":\"15701\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b7e57cb8-06aa-4404-8b00-e1ca9710d87d>\",\"WARC-Concurrent-To\":\"<urn:uuid:9f1be291-f602-4e28-b6d5-c4f0afd76e0d>\",\"WARC-IP-Address\":\"150.203.186.177\",\"WARC-Target-URI\":\"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p53\",\"WARC-Payload-Digest\":\"sha1:GVJ72LKXQ5MTD4P5WKQCALNJE23VTOFA\",\"WARC-Block-Digest\":\"sha1:F4IG7PMBJFO2S65DIWF7T5TUM6XH243V\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-49/CC-MAIN-2021-49_segments_1637964360803.6_warc_CC-MAIN-20211201143545-20211201173545-00598.warc.gz\"}"}