Need a hint for an expected value problem

Question

You are allowed to write positive integers from 1 to 100 on 100 cards, you the show the 100 cards to a friend who will pick a number. You then shuffle the deck and flip off the top card. If the top card was the number your friend selected you pay him that number. Assuming your friend picks the number to maximize his expected value what numbers do you place on each of the 100 cards to minimize his expected value

My strategy was to start from the highest number we can place in the deck and go down. For example we can't place a hundred in the deck because this would give an expected value of 1 if the friend picked 100, but this isn't giving me much progress. Any suggestions are appreciated

Answer 1

Assuming there are $k$ copies of a card with value $n$ in the deck, the expected value of picking that card is $\frac{kn}{100}$.

Suppose there is some optimal expected value $v$. Then we know that $\frac{kn}{100} \leq v$. But we can rearrange that to $k \leq \frac{100v}{n}$.

So if we assume $v = \frac12$ we find that for $n = 1$ we can use up to $k = 50$ cards. And continuing we find that we use $50, 25, 16, 9$ cards of respectively $1, 2, 3, 4$ by choosing the highest value of $k$ possible for each $n$, and this reaches $100$ cards.

If we assume $v$ small enough we won't be able to reach $100$ cards because the limits on $k$ become too tight. So there must be some smallest $v$ that's feasible.

Does this help? Spoiler for $v$:

$v$ = 0.28 is optimal.

Answer 2

HINT

If you write down all the numbers $1$ through $100$, then your friend will of course pick $100$ and has an expected payoff of $1$.

Can you do better? Sure, don't include $100$ ... but that means you have to have some number twice. No problem, just have two $1$'s ... your friend has twice the chance of winning when picking $1$, but since the payout is so low, that gives an expected payoff of $0.02$, and so your friend is far better off picking $99$ ... which has an expected payoff of $0.99$. Of course, even better would be to have three $1$'s and have $98$ be the highest ... but if you go all the way and get just $100$ $1$'s, then your friend will pick $1$, and is certain to win $1$. So, I think you now see where this is going: Try to strike a balance between avoiding using high numbers, and how many multiples of the low numbers you are using.

In fact, here is what you need to do: have a whole bunch of $1$'s ... and a good bunch of $2$'s, a decent amount of $3$'s, etc. Where of course you try to make the expected payoff roughly the same for each number.

Answer 3

First, you must have at least one $1$ in your deck, because if you didn’t, you could subtract $1$ from each card to get a deck that has lower expected values for each possible value. In a similar fashion, you should be able to convince yourself that you must use the first $k$ integers, for some $k\leq 100$.

Now, notice that if your friend picks the number $\ell$ and there are $c_{\ell}$instances of $\ell$ in the deck, the expected value is $(c_\ell/100)\ell$. so if there are $c_1$ $1$’s, $c_2$ $2$’s, all the way up to $c_k$ $k$’s, you essentially want to make sure that $(c_i/100)i$ is about the same for any $i$.

Thus informally we want $c_1\approx 2c_2\approx...\approx kc_k$. If $c_1+c_2+\dots+c_k=100$, can you figure out good choices for the $c_i$’s?