12
$\begingroup$

There is a game with $10$ cards(cards are number $1$ to $10$). They are distributed to $2$ players randomly. Player who has the highest sum of card values wins the game.

Now, before the cards are dealt, player A will say a number. This number is the number of cards he will RANDOMLY pull from player B, and then return the cards of his choice to player B.(The cards returned cannot be the cards he has taken from player B).

So, what is the number of cards player A should pull from player B to maximize his chances of winning the game?

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

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

I assume that there is a unimodal winning probability with the peak at the centre.

However, I am facing difficulty in which one of these $2$ will be larger and by how much?

Part $2$ - Can this be generalised to '$n$' cards?

$\endgroup$
22
  • 2
    $\begingroup$ Side note; it is not obvious (to me) that swapping $1$ is the same as swapping $4$. Same with $2,3$. $\endgroup$
    – lulu
    Jun 9, 2021 at 15:15
  • 2
    $\begingroup$ I did a brute-force calculation. Swapping $1$ card wins $79.92\%$ of the time, and swapping $2$ cards wins $92.38\%$ of the time. Sure enough, swapping $4$ cards is the same as swapping $1$ and swapping $3$ is the same as swapping $2$, but I can't see the reason for this symmetry. Please explain it. $\endgroup$
    – saulspatz
    Jun 9, 2021 at 16:09
  • 1
    $\begingroup$ @BarryCipra Not sure what your list is. Should $\{1,3,4\}\to \{2,3,4\}$ appear on it? $\endgroup$
    – lulu
    Jun 10, 2021 at 14:09
  • 1
    $\begingroup$ @lulu, yes, it should, as should $\{1,3,5\}\to\{2,3,5\}$. Including those lowers the probablity to $52/60=13/15$. Thank you for doublechecking! $\endgroup$ Jun 10, 2021 at 14:32
  • 2
    $\begingroup$ @antkam By symmetry, winning by swapping your lowest i cards is the same as losing by swapping your highest i cards. But then swap hands, and it is the same as winning by swapping your lowest N-i cards. $\endgroup$
    – Empy2
    Jun 18, 2021 at 3:27

1 Answer 1

5
$\begingroup$

I wrote the following Matlab routine, to find answers for 2 cards up to 20 cards.

> for H=2:2:20   
>    S=nchoosek(1:H,H/2);   
>    SH=sum(1:H)/2;  
>    disp(num2str(H));    
>    for k=1:H/2,      
>       P=nchoosek(1:H/2,k);      
>       M=0; 
>       for n=1:size(S,1),   
>          v=1:H;w=S(n,:);
>          v(w)=[];  
>          x=v(P);  if k==1,x=x(:);end;  
>          t=sum(w(k+1:end))+sum(x,2);   
>          M=M+[sum(t<SH) sum(t==SH) sum(t>SH)];
>       end;   
>       disp(num2str(M));  
> end;end;  
> 
> 2 
> 1  0  1
> 1  0  1 
> 4  
> 2  2  2
> 1  4  7 
> 2  2  2 
> 6  
> 10   0  10
> 11   0  49 
> 11   0  49 
> 10   0  10 
> 8  
> 31    8   31
> 41   26  213 
> 26   30  364 
> 41   26  213 
> 31    8   31 
> 10 
> 126     0   126
> 253     0  1007 
> 192     0  2328 
> 192     0  2328 
> 253     0  1007 
> 126     0   126 
> 12 
>  433    58    433
> 1046   280   4218 
>  862   406  12592 
>  608   376  17496 
>  862   406  12592 
> 1046   280   4218 
>  433    58    433 
> 14 
> 1716       0    1716
> 5390       0   18634 
> 5851       0   66221 
> 3994       0  116126 
> 3994       0  116126 
> 5851       0   66221 
> 5390       0   18634
> 1716       0    1716 
> 16 
>  6172    526    6172
> 22468   3434   77058 
> 28359   6944  325057 
> 19791   7058  693871 
> 14784   6200  879916 
> 19791   7058  693871 
> 28359   6944  325057 
> 22468   3434   77058 
>  6172    526    6172 
> 18 
>  24310       0    24310
> 106695       0   330885
> 166884       0  1583436 
> 137540       0  3946540 
>  93424       0  6032696 
>  93424       0  6032696 
> 137540       0  3946540 
> 166884       0  1583436 
> 106695       0   330885 
>  24310       0    24310 
> 20 
>  89654      5448     89654
> 443606     45390   1358564 
> 794383    123079   7396558 
> 732360    161012  21277348
> 483565    138654  38176541 
> 378539    120244  46059729 
> 483565    138654  38176541 
> 732360    161012  21277348 
> 794383    123079   7396558 
> 443606     45390   1358564 
>  89654      5448     89654

The mean of the sum, with 2n cards, and swapped k of them, is $$\frac{n(2n+1)}2+\frac{2n+1}{2n+2}k(n-k)$$ The variance of the sum is $$-\frac{(2n+1)(7n+4)}{12(n+1)^2(n+2)}k^2(n-k)^2 -\frac{(2n+1)(3n+1)}{6(n+1)(n+2)}k(n-k) +\frac{n^2(2n+1)}{12}$$ I then used the Gaussian approximation, assuming the mean and variance with enough cards would look normally distributed. I plotted the Matlab formula $$1/2+(1/2)erf((Mean-250250)./sqrt(2*Var))$$ on the same graph as simulations and got this result. Simulations were 100000 deals of 1000 cards (500 each), and each deal was calculated for all values of k.

enter image description here

The following was the difference, after 100000, between swapping i cards and swapping 500-i cards. Note, the same deals were used for different numbers of swapped cards, so there is a strong correlation between i and i+1. The difference between i and 500-i was less than one percent.

enter image description here

The nearest integers to the Gaussian estimates are given below, and can be compared with exact counts given above:

> 2  
> 1  1  
> 1  1
> 4  
> 3   3  
> 2  10  
> 3   3  
> 6  
> 10  10  
> 10  50  
> 10  50  
> 10  10  
> 8  
> 35   35  
> 50  230  
> 35  385  
> 50  230  
> 35   35  
> 10  
> 126   126  
> 243  1017  
> 172  2348  
> 172  2348  
> 243  1017  
> 126   126  
> 12  
>  462    462  
> 1144   4400  
>  951  12909  
>  696  17784  
>  951  12909  
> 1144   4400  
>  462    462  
> 14  
> 1716    1716  
> 5257   18767  
> 5353   66719  
> 3548  116572  
> 3548  116572  
> 5353   66719  
> 5257   18767  
> 1716    1716  
> 16  
>  6435    6435  
> 23674   79286  
> 29434  330926  
> 20419  700301  
> 15638  885262  
> 20419  700301  
> 29434  330926  
> 23674   79286  
>  6435    6435  
> 18  
>  24310    24310  
> 104955   332625  
> 156872  1593448  
> 121991  3962089  
>  81882  6044238  
>  81882  6044238  
> 121991  3962089  
> 156872  1593448  
> 104955   332625  
>  24310    24310  
> 20  
>  92378     92378  
> 459615   1387945  
> 811462   7502558  
> 725557  21445163  
> 477390  38321370  
> 379665  46178847  
> 477390  38321370  
> 725557  21445163  
> 811462   7502558  
> 459615   1387945  
>  92378     92378  
$\endgroup$
0

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.