100 blank cards, minimize the EV

I give you a hundred blank cards, and you can write a single positive integer on each card. I look at the cards when you are done, then I shuffle the deck. I guess the top card of the deck, and if I am right, I make the dollar which is written on the card. What numbers should you write on the cards to minimize the expected return of mine?

Attempt: So this problem seems to me quite difficult. If I put a 1 on a cards, then the Expected value is 1. if I put two 2s, and the rest 1-99, the Expected value is 99/100.

I feel the minimum occurs when i is an integer on at least one of the cards, where $ip_{i} = jp_{j}$ for every i,j is nearly satisfied, otherwise you could minimize it further. So p1=2p2 = 3p3 =...=npn

So if you used only 1 and 2, then could get EV close to 2/3.

So to solve this I feel I need to work out the minimum G such that,

p1 ≈ p2 ≈ p3 ≈ .. ≈ pn ≈ G

where you cannot reorganise the cards, to make a closer approximation.

Solution 1:

To solve this question, it comes down to finding the number of $1$s we should use, defined as $x$. We can then assign $\lfloor\frac{x}{2}\rfloor$ $2$s, $\lfloor\frac{x}{3}\rfloor$ $3$s and so on. We must now minimize $x$, given that the total sum must be greater than or equal to $100$:

$$min(x): \sum_{i=1}^{100}\left\lfloor\frac{x}{i}\right\rfloor \ge 100$$

The lowest integer $x$ for which this is true is $28$, resulting in a total sum of $101$. The expected value then equals $0.28$ when the person guesses $1$, and $0.28$ or lower for every other number.

Solution 2:

Yes, you have the right idea: With $p_i$ the probability of drawing a card with number $i$, the expected value of choosing $i$ is $p_i \cdot i$, and you want to make this roughly equal for any $i$. Or, to be more exact: you want to find a value $E$ so that $p_i \cdot i$ is always smaller or equal to $E$ for all $i$.

Just by playing around a bit, I found that you can always get $p_i \cdot i$ at or below $0.28$:

$28$ cards with the number $1$

$14$ cards with the number $2$

$9$ cards with the number $3$

$7$ cards with number $4$

$5$ cards with number $5$

$4$ cards each for numbers $6$ and $7$

$3$ cards each for numbers $8$ and $9$

$2$ cards each for numbers $10$ through $14$

$1$ cards each for numbers $15$ through $27$

For a total of $28+14+9+7+5+2\cdot 4+2\cdot 3 + 5 \cdot 2 + 13=100$ cards, and the best the person can do here is to get an expected value of $0.28$ by picking any of the numbers $1$,$2$,$4$,$7$, or $14$.

Also, it is clear that this is the best you can do: to do better, you'd need to get $27$ cards of $1$, $13$ with $2$ ... and already you'd need a card with $29$. So, the best you can do is to write the numbers as spelled out above.