5
$\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, 2021 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, 2021 at 2:18
  • $\begingroup$ @Ankit, yes each player gets 5 cards. $\endgroup$ Jul 4, 2021 at 3:52
  • $\begingroup$ Yes, understanding is correct. Also, player A cannot give the same cards he received from B $\endgroup$ Jul 4, 2021 at 3:53
  • 1
    $\begingroup$ I made an edit with the clarifications $\endgroup$
    – Ankit
    Jul 4, 2021 at 4:06

3 Answers 3

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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 10:51
  • $\begingroup$ Yeah me too I mean, I assumed it to have uni modal distribution, but this is interesting $\endgroup$ Jul 4, 2021 at 13:35
  • 1
    $\begingroup$ Lmao I used Java to try to prove it and I crashed the compiler. $\endgroup$
    – Ankit
    Jul 4, 2021 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, 2021 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, 2021 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, 2021 at 8:07
  • $\begingroup$ Yeah, you kinda solved the entire problem just by deducing Sherlock ;) $\endgroup$ Jul 6, 2021 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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