, 2014

We need at least $\frac{n(n-1)}{2} + 1$ cards.

For example, we can have $i$ cards with number $i!$ for each $i = 1, 2, \dots, n-1$ and another card with number $n!$. For $t = n!$, we can simply choose the card with number $n!$. Suppose that $1 \le t < n!$. Let $r_0 = t$, and for $i = 1, 2, \dots, n-1$, define integers $q_i$ and $r_i$ inductively, using the division algorithm:
$$r_{i-1} = q_i(n-i)! + r_i, \quad 0 \le r_i < (n-i)!.$$
Then $t = \sum_{i=1}^{n-1} q_i(n-i)!$. Since $r_{i-1} < (n-i+1)!$, we have that $q_i \le n-i$. Thus, we can choose $q_i$ cards with number $(n-i)!$ for each $i = 1, 2, \dots, n-1$ so that the sum of the numbers is $t$. So the required properties are satisfied.

Next, consider the smallest set of cards we can make with numbers adding up to $n! - 1$. Clearly, this set cannot contain any card with number greater than $(n-1)!$. For each $i = 1, 2, \dots, n-1$, let $c_i$ be the number of cards with number $i!$ in this set. Then $c_i \le i$ for all $i$, for if $c_i \ge i+1$ then we can replace $i+1$ cards with number $i!$

in this set with just one card with number $(i + 1)!$, contradicting the minimality of the set. So now we have that
$$n! - 1 = \sum_{i=1}^{n-1} c_i i! \le \sum_{i=1}^{n-1} i(i!) = \sum_{i=1}^{n-1} ((i + 1)! - i!) = n! - 1.$$
This implies that all inequalities involved must be equality; that is, $c_i = i$ for all $i$. Thus, this set has $1 + 2 + \dots + (n - 1) = \frac{n(n-1)}{2}$ cards.

Suppose now that we have a collection of cards with the required properties. Then some of these cards have numbers adding up to $n! - 1$. So by what we have just shown, this collection must contain at least $\frac{n(n-1)}{2}$ cards. However, if we have exactly $\frac{n(n-1)}{2}$ cards, then we must select all these cards for the sum of the numbers to be $n! - 1$, but this means that we cannot select cards for the sum of the numbers to be $n!$, a contradiction. Therefore we need at least $\frac{n(n-1)}{2} + 1$ cards. $\square$