4
$\begingroup$

Ten cards, numbered 1-10, are randomly dealt to 2 players, A and B, such that each player gets 5 cards.

Before the cards are dealt, player A will say a number N. After the cards are dealt, A will randomly take N cards from B, and choose N cards from A's original hand to give back to B.

The winner is the player who has the highest sum of card values after the swap.

What number should A call to maximize his chances of winning the game?

Example Case 1

If Player A says 0, his winning probability remains at 0.5

Example Case 2

If Player A says 5, he takes all of B's card, and give all of his cards to B. His winning probability remains at 0.5 again

$\endgroup$
8
  • $\begingroup$ Wait so essentially Player A is randomly taking x cards from B's deck, and chosing x cards to give back to Player B. Is that correct? $\endgroup$
    – Ankit
    Jul 4 '21 at 2:17
  • $\begingroup$ Also when you say that the cards are randomly assigned, each player will get 5 cards right? $\endgroup$
    – Ankit
    Jul 4 '21 at 2:18
  • $\begingroup$ @Ankit, yes each player gets 5 cards. $\endgroup$ Jul 4 '21 at 3:52
  • $\begingroup$ Yes, understanding is correct. Also, player A cannot give the same cards he received from B $\endgroup$ Jul 4 '21 at 3:53
  • 1
    $\begingroup$ I made an edit with the clarifications $\endgroup$
    – Ankit
    Jul 4 '21 at 4:06
8
$\begingroup$

Here's my solution based on expectations.

First,

we calculate the expected value of the smallest, second-smallest, third-smallest... number on the 5 cards drawn.

The calculation steps are shown below:

$$E(\text{smallest})=\dfrac{1\times \dbinom{9}{4}+2\times \dbinom{8}{4}+\cdots+6\times \dbinom{4}{4}}{\dbinom{10}{5}}=\dfrac{11}{6}.$$
Explanation: the numerator basically sums the smallest terms in all 5-card draws, and the denominator is the total number of cases.
Similarly, we have
$$E(\text{second-smallest})=\dfrac{2\times \dbinom{8}{3}\times \dbinom{1}{1}+3\times \dbinom{7}{3}\times \dbinom{2}{1}+\cdots+7\times \dbinom{3}{3}\times \dbinom{6}{1}}{\dbinom{10}{5}}=\dfrac{11}{3};$$
$$E(\text{third-smallest})=\dfrac{3\times \dbinom{7}{2}\times \dbinom{2}{2}+4\times \dbinom{6}{2}\times \dbinom{3}{2}+\cdots+8\times \dbinom{2}{2}\times \dbinom{7}{2}}{\dbinom{10}{5}}=\dfrac{11}{2};$$
$$E(\text{fourth-smallest})=\dfrac{4\times \dbinom{6}{1}\times \dbinom{3}{3}+5\times \dbinom{5}{1}\times \dbinom{4}{3}+\cdots+9\times \dbinom{1}{1}\times \dbinom{8}{3}}{\dbinom{10}{5}}=\dfrac{22}{3};$$
$$E(\text{fifth-smallest, or largest})=\dfrac{5\times \dbinom{4}{4}+6\times \dbinom{5}{4}+\cdots+10\times \dbinom{9}{4}}{\dbinom{10}{5}}=\dfrac{55}{6}.$$
As a quick double check, adding them all together yields $27.5$, which is the expected sum of the 5 cards.

Next, let's think about A's strategy.

In essence, he is discarding his $N$ smallest cards to get random cards. Thus, if the expected value of cards that he is discarding is smaller than the expected value of cards he is getting, then A is benefitting. The more A benefits, the higher his chances of winning.

Then,

clearly $E(\text{smallest})$, $E(\text{second-smallest})$ are smaller than $5.5$, the expected value on a random card. $E(\text{third-smallest})$ is equal to $5.5$, and $E(\text{fourth-smallest})$, $E(\text{fifth-smallest, or largest})$ are greater than $5.5$.
This means that discarding the smallest card and discarding the second smallest card are moves with expected benefits, discarding the third smallest card will bring no benefit nor loss, and discarding the two largest cards will expectedly result in loss.

In conclusion:

When $N=2,3$, A has the maximal chance of winning the game.

$\endgroup$
9
  • $\begingroup$ Wow, I really like your thought process of calculating E(smallest) $\endgroup$ Jul 4 '21 at 13:37
  • $\begingroup$ This works I guess because the difference between 2 or 3 and 1 or 4 is quite big. But I guess perhaps we need to also consider that when A gets some cards, while discarding the lowest numbers, the random cards to be obtained should be related to his current hand. For example, if A's hand is 1,2,3,4,5, the random card A is getting has expectation 8. Of course, overall, the expectation is still 5.5, but in each cases it would have different probability of winning. $\endgroup$
    – justhalf
    Jul 4 '21 at 13:45
  • $\begingroup$ @justhalf That's true, but remember that N is chosen before any cards has been drawn, meaning that we have to look at the case averagely. $\endgroup$
    – Jerry Dean
    Jul 4 '21 at 15:49
  • $\begingroup$ We have to look at the combined probability, not averaged probability =) For example, if the question were instead asking about the probability of getting 5 even-numbered cards, then the calculation for each hand will be different. $\endgroup$
    – justhalf
    Jul 4 '21 at 16:14
  • $\begingroup$ @justhalf for each hand yes, but since we are finding the optimal N here, we probably shouldn't analyze specific cases. $\endgroup$
    – Jerry Dean
    Jul 4 '21 at 16:15
6
$\begingroup$

I wasn't fast enough, but here's some code confirming Jerry's answer:

from itertools import combinations
wins = [0]*6
total = [0]*6
for A in combinations(range(10),5):
    rem = set(range(10))-set(A)
    for N in range(6):
        for draw in combinations(rem,N):
            total[N] += 1
            if sum(A[N:]+draw) > 22: wins[N] += 1
for i in range(6): print(i,wins[i]/total[i])  

which gives the following output:

50% chance for 0 and 5, 79.92% chance for 1 and 4, and 92.38% chance for 2 and 3.

$\endgroup$
5
  • 1
    $\begingroup$ 90%?! I didn't expect the probability to be that high! :o $\endgroup$
    – Jerry Dean
    Jul 4 '21 at 10:51
  • $\begingroup$ Yeah me too I mean, I assumed it to have uni modal distribution, but this is interesting $\endgroup$ Jul 4 '21 at 13:35
  • 1
    $\begingroup$ Lmao I used Java to try to prove it and I crashed the compiler. $\endgroup$
    – Ankit
    Jul 4 '21 at 15:24
  • $\begingroup$ @Ankit there must be some bug somewhere. The number of cases is only 10C5 = 252 times the number of cards randomly picked by A, 5C1+5C2+5C3+5C4 = 30. So 7560 cases total. $\endgroup$
    – justhalf
    Jul 4 '21 at 18:36
  • $\begingroup$ I counted 8064, interestingly. Perhaps Ankit was trying to simulate all discards by A instead of just going with the best possible one? $\endgroup$ Jul 5 '21 at 14:31
3
$\begingroup$

There are already a couple of answers, but I think this question is a bit better than just a straightforward calculation problem, so here's one more.

You can reword the question into 5 separate questions like this:

  1. Here is a card of which you know nothing, except that it was the smallest in a random sample of 5 cards. Do you wish to exchange it for a card of which you do not have this information?
  2. Here is a card of which you know nothing, except that it was the second smallest in a random sample of 5 cards. Do you wish to exchange it for a card of which you do not have this information?
  3. And so on.

Casually slathering some Bayes onto the given information, then, we get that the cards that were smaller than average in the random sample are more likely to be smaller than average in actuality too, and vice versa.

Since we expect the cards that we know nothing about to be "average" by definition, we should exchange two of the smallest cards for certain, and the two biggest cards never.

The middle card in our hand is a bit trickier. Luckily, the problem has many symmetries, so we can reason that we got exactly the same information about the card being small and the card being big (there are two smaller cards, and two larger cards), so whatever the likelihood distribution, it is going to be symmetrical, and therefore the expected size of the third card should still be "average".

So exchanging the third card would only affect our hand's likely deviation from the point value average, and not the expected point value of the hand itself.

In conclusion, to maximize our hand's point value,

we should exchange either 2 or 3 cards.

Interestingly, we never used the total number of cards in this reasoning, so this strategy should maximise our points no matter how many cards in the deck. (As long as the cards are numbered with unique, consecutive integers, or in another suitably symmetrical manner.)

$\endgroup$
2
  • $\begingroup$ Nice reasoning! $\endgroup$
    – justhalf
    Jul 6 '21 at 8:07
  • $\begingroup$ Yeah, you kinda solved the entire problem just by deducing Sherlock ;) $\endgroup$ Jul 6 '21 at 16:47

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.