Minimax Card Number Assignment
You have 100 cards and must assign each card a number from 1 to 5. Once you have fixed your assignment, an opponent draws a card uniformly at random and guesses the number written on it. If the guess is correct, you pay the opponent an amount equal to that number; if the guess is wrong, you pay nothing.
The opponent knows your full distribution (i.e., how many cards carry each number) and will choose whichever guess maximizes their expected payoff.
How should you distribute the numbers across the 100 cards to minimize your expected loss? What is the resulting expected loss per draw?
Hints
- Think about what the opponent will do: they pick whichever guess $k$ maximizes $k \cdot n_k$. So you want no single product to stick out.
- Try to equalize the products $k \cdot n_k$ across all values of $k$. That means assigning counts inversely proportional to the card values: $n_k \propto 1/k$.
- Use the constraint $\sum n_k = 100$ with $n_k = C/k$ to solve for $C = 6000/137 \approx 43.8$, then round to integers and check which guess the opponent exploits.
Worked Solution
How to Think About It: This is a classic minimax problem. You pick a distribution, then the opponent best-responds. The opponent will always guess the number $k$ that maximizes $k \cdot n_k / 100$, where $n_k$ is how many cards carry value $k$. So your expected loss is $\max_k\, k \cdot n_k / 100$. You want to choose the $n_k$ values to make that maximum as small as possible. The key intuition: if one product $k \cdot n_k$ sticks out above the rest, the opponent exploits it. So you want to equalize all the products.
Quick Estimate: If we set $k \cdot n_k = C$ for every $k$, then $n_k = C/k$, and the constraint $\sum n_k = 100$ gives
$$C\left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5}\right) = 100.$$
The harmonic piece is $1 + 0.5 + 0.333 + 0.25 + 0.2 = 137/60 \approx 2.283$, so $C = 100 / 2.283 \approx 43.8$. That means the expected loss is roughly $C/100 \approx 0.438$. But since the $n_k$ must be integers, we will not hit this exactly.
Approach: Solve the continuous relaxation (set $k \cdot n_k$ constant), then round to integers and check which guess the opponent exploits.
Formal Solution:
Let $n_k$ be the number of cards with value $k$. The opponent's expected payoff from guessing $k$ is $k \cdot n_k / 100$. They pick $\arg\max_k\, k \cdot n_k$. We want to minimize $\max_k\, k \cdot n_k$ subject to $\sum_{k=1}^{5} n_k = 100$, $n_k \geq 0$, $n_k \in \mathbb{Z}$.
Continuous relaxation: set $k \cdot n_k = C$ for all $k$, so $n_k = C/k$. Summing:
$$\sum_{k=1}^{5} \frac{C}{k} = C \cdot \frac{137}{60} = 100 \implies C = \frac{6000}{137} \approx 43.80.$$
The ideal (non-integer) counts are $n_1 = 43.80$, $n_2 = 21.90$, $n_3 = 14.60$, $n_4 = 10.95$, $n_5 = 8.76$.
Rounding to integers while keeping the sum at 100, a natural choice is:
| $k$ | $n_k$ | $k \cdot n_k$ | |-----|--------|----------------| | 1 | 44 | 44 | | 2 | 22 | 44 | | 3 | 15 | 45 | | 4 | 11 | 44 | | 5 | 8 | 40 |
Total cards: $44 + 22 + 15 + 11 + 8 = 100$. The products are $\{44, 44, 45, 44, 40\}$. The opponent guesses $k = 3$ (the largest product, 45) and the expected loss is $45/100 = 0.45$.
Can we do better? Try shifting one card from $k = 3$ to $k = 5$: $n_3 = 14$, $n_5 = 9$. Then $3 \times 14 = 42$, $5 \times 9 = 45$ -- no improvement; the max is still 45. Try $n_1 = 43$, $n_3 = 15$, $n_5 = 9$: $1 \times 43 = 43$, $3 \times 15 = 45$, $5 \times 9 = 45$ -- the max is still 45. Due to the integer constraint, you cannot push the maximum product below 44, and the rounding of $n_3$ forces it to 45 (since $14 \times 3 = 42$ would make other counts push past 44 elsewhere). The distribution $(44, 22, 15, 11, 8)$ is optimal or within one unit of optimal.
Answer: Assign $n_1 = 44$, $n_2 = 22$, $n_3 = 15$, $n_4 = 11$, $n_5 = 8$ cards to values 1 through 5 respectively. The counts are inversely proportional to the card values (the equalizing principle $n_k \propto 1/k$). The opponent is nearly indifferent across guesses, and your minimax expected loss is $\mathbf{0.45}$ per draw.
Intuition
This is the equalizing principle at the heart of minimax strategy: when your opponent can exploit any imbalance, the optimal defense is to remove all imbalances. Here the opponent targets whichever value $k$ has the largest product $k \cdot n_k$, so you want to flatten those products. That forces the counts to be inversely proportional to the payoffs -- higher-payoff numbers appear on fewer cards. The result is that the opponent gains almost nothing from their knowledge of your distribution, because every guess yields roughly the same expected payoff.
This pattern shows up constantly in quantitative work. Market makers setting quotes across strike prices, poker players balancing bluff-to-value ratios, and portfolio managers allocating risk across correlated bets all face the same structure: an adversary (the market, an opponent, tail risk) will exploit the weakest link, so you equalize exposure across all links. The common mistake is to think you should minimize the total expected payoff in a cooperative sense -- but because the opponent best-responds, minimizing the maximum is what matters.