Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $N$ cards numbered $1,\dots,n$. Let us call each number a denomination. These are distributed among two persons A and B. There can be more than one cards having same number. Socring is done as follows:

If $a_i > b_i$ then A scores $|a_i-b_i|$ where $a_i$ is the number of $i^{th}$ numbered cards with A and $b_i$ is the number of $i^{th}$ numbered cards with B for every denomination.

If $b_i > a_i$ then B scores $|a_i-b_i|$ where $a_i$ is the number of $i^{th}$ numbered cards with A and $b_i$ is the number of $i^{th}$ numbered cards with B for every denomination.

The final score of a player is sum scores of all denomination. The player with highest aggregate score wins. Find the number of ways player A can win.

share|improve this question
    
How does scoring work? Do both parties get scored $|a_i - b_i|$? Or do they get that score for each of the $i$th card that they hold? E.g. if A has 1, 1, 1, 1, 1, and B has 1, 1, 2, what's the score? And what do you mean by "number of ways player A can win"? are the labels on the N cards known? If ties are unlikely, then A has about $2^{N-1}$ ways to win. –  Calvin Lin Feb 4 '13 at 0:47
    
@CalvinLin edited the question. Apologize for mistake. –  Aman Deep Gautam Feb 4 '13 at 1:13
    
Do you mean that $N$ is even, and A and B each receive $N/2$ cards? –  Brian M. Scott Feb 4 '13 at 1:18
    
@BrianM.Scott Why do we have to put a constraint on N. I did not get you. –  Aman Deep Gautam Feb 4 '13 at 1:20
    
How are the cards distributed to A and B? Does each get the same number of cards? Are all $N$ cards distributed? If the answers to those questions are yes, you need the constraints that I suggested. If not, you need to explain more. –  Brian M. Scott Feb 4 '13 at 1:21
show 3 more comments

1 Answer 1

up vote 1 down vote accepted

If I understand the game correctly,

$$\sum_{k=1}^n(a_k-b_k)=\sum_{k=1}^n(2a_k-m_k)=2\sum_{k=1}^na_k-\sum_{k=1}^nm_k=2\sum_{k=1}^na_k-N\;,$$

where $m_k$ is the number of cards of the $k$-the denomination. Thus, A wins iff $$2\sum_{k=1}^na_k>N\;,$$

or $$\sum_{k=1}^na_k>\frac{N}2\;,$$

i.e., precisely when he has more than half of the cards. If $N$ is odd, exactly half of the subsets of the deck have more than $N/2$ cards, and A will win with probability $\frac12$. If $N$ is even, the $\binom{N}{N/2}$ subsets of cardinality $N/2$ result in ties, so A wins with

$$\frac12\left(2^N-\binom{N}{N/2}\right)$$

hands and hence with probability $$\frac12-\frac1{2^{N+1}}\binom{N}{N/2}\;.$$

share|improve this answer
    
That I figured out on my own. What's next. I mean that since the cards of same denomination are identical I can't use direct C(n,k) formula. –  Aman Deep Gautam Feb 4 '13 at 1:45
    
@Aman: See my addition. The point is that the identities of the cards don’t matter at all. –  Brian M. Scott Feb 4 '13 at 1:53
    
I still do not understand. Please bear with me. Here is what I do not understand. Let us have two denominations $1$ and $2$. Now let there be 5 cards, namely, $1, 1', 1'', 2, 2'$ ($'$ are included just to differentiate cards of same denomination for discussion purposes). If choose a combination $1, 1', 2, 2'$ and $1', 1'', 2, 2'$ for A then this is only a way of winning(counted 2 times, if I use normal C(n, k) formula without any constraints.) as A has 2 cards of denomination 1 and 2 cards of denomination 2. –  Aman Deep Gautam Feb 4 '13 at 2:04
    
@Aman: If A has at least $3$ of those $5$ cards, he wins, full stop. Are you interested in counting the number of distinct permutations of winning hands, and not just the number of winning hands? –  Brian M. Scott Feb 4 '13 at 2:10
    
I wanted to count the number of ways $A$ win. And I think that it should be equal to the number of distinct permutations only. Am I thinking correctly? –  Aman Deep Gautam Feb 4 '13 at 2:13
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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