The n-Card Problem

Suppose I have n cards, each of which contains n non-negative real numbers that sum to 1 written in a row. I arrange the cards, one below the next, in some order and then calculate the sum of the numbers appearing on the diagonal. What are the minimal closed intervals such that, no matter what numbers are written on the cards, there is some permutation of the cards whose diagonal sum is contained in the interval? This is the n-card problem, which is closely related to classical industrial and management problems such as the linear assignment problem and the travelling salesman problem.

The minimal intervals for the n-card problem are known only for n ≤ 4. In 2012, Justin Chan and I introduced a new method of analysis for the n-card problem, involving repeated use of the Extreme Principle from problem-solving folklore. We used this method to show that [1, 2] is a minimal interval for every n, answering a 2011 question due to Sands. We also showed that each closed interval of length n/(n-1) contained in [0, 2] is a minimal interval for every n.

A set of 4 cards
Four cards, whose diagonal sum under all 24 permutations is one of 12, 56, 76, 32, 116.