9
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok interesting, this is a nice problem, I was kind of on the right track, I am just trying to figure out why definitely 0.28 is the minimum, I can see it is the minimum if we don't skip a positive integer. Because as you say, then we would need to reduce the 28 cards of 1, and increasing any other card, ruins it. $\endgroup$ – Tinatim Jun 22 '18 at 11:52
  • $\begingroup$ @Tinatim Right, and if you skip a number, you're making it even worse, because then the highest card would be at least 28. And if you have at least one card of 28 or higher, then the other person can pick that one and get an EV of at least 0.28. $\endgroup$ – Bram28 Jun 22 '18 at 11:57
  • $\begingroup$ Doh, silly me. I see, this was a nicer problem than I expected, and 0.28 is definitely the best!! $\endgroup$ – Tinatim Jun 22 '18 at 12:10
  • $\begingroup$ @Tinatim Yeah, it was fun finding that number 28 ... which happens to be my favorite number :) $\endgroup$ – Bram28 Jun 22 '18 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.