Even Number cards?

Question

There are $15$ cards on a table, marked with an integer $1$ from to $15$ . How many ways can I take cards such that the sum of the numbers on the cards is even? Please help me?

Answer 1

Hint: For any subset of the first $14$ cards ($1, 2,..., 14$), there is exactly one way to complete it by using or not using card $15$, so as to make the sum even.

Answer 2

Hint: 7 cards have even numbers and 8 cards have odd numbers. You can take any of the even cards, and you must take an even number of the odd cards. Calculate these two amounts separately, then multiply.

Answer 3

Generating function approach.

Let $$f(x)=\prod_{i=1}^{15} \left(1+x^i\right)=\sum_{j=0}^{15\cdot 16/2} a_jx^j$$

where $a_j$ is the number of ways of getting a total of $j$ from taking cards.

Then you are looking for $\frac{f(1)+f(-1)}{2}$. But $f(-1)=0$, so you are looking for $\frac{f(1)}{2}=2^{14}$.

That includes taking zero cards to get zero, so you might want the answer $2^{14}-1$.

Answer 4

Using the fact that sum of two odd cards is even or a single even card is even.If you want even cards you must take these in these quanta.

The number of ways in which you can take even cards(total 7) is [none or more]: $$2^7=128\text{ ways }$$ The number of ways in which you can take pairs of odd cards(total 8 cards, 4 pairs at a time) is same as taking even quantity of odd faced cards, i.e.: $$\sum_{k=0}^{4}\binom8{2k}=2^{7}=128\text{ ways }\quad\left(\because \sum_{k=0}^{n/2}\binom n{2k}=2^{n-1}\right)$$ Total $2^7.2^7-1=2^{14}-1=16383$, [ minus one the case in which both quanta have zero cards.] Similiarly it can be showed that for n cards it is $2^{n-1}-1$

Answer 5

An opportunistically easy Olympiad-style smartass proof of the general result derived by Aditya (which we could also have gotten directly from symmetry of Pascal's triangle)

• In the general case with n cards, there are $2^n$ ways of picking a subset partition (for now, include the empty set).
• In our specific case n=15, there is an even number of odd cards, of which we are constrained to pick an even-numbered subset of odd cards, and any number of even cards.
• But note that for every valid partition $P = \{p_i\}$ there exists exactly one corresponding partition $P'$ which is invalid; we can choose to construct $P'$ by either $P' = U \setminus P$ or $P' = \{15 - p_i\}$. (Both are invalid because both change the number of odd cards (since n=15 had an odd number of odd cards. If n was even this would be slightly harder).
• Hence $#P = #P'$. Since $#P + #P' = 2^n$, it follows that $#P = 2^n-1 -1$ (where we finally exclude the empty set).