# Number of ways of winning a particular kind of game

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.

-
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

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}\;.$$

-
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