5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'm sure this is an effective duplicate of previous questions. Hint: Consider the sets which do or don't contain $1$. $\endgroup$ – Mark Bennet Nov 6 '14 at 22:35
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this very much; you could probably also say that due to "symmetry", half of the subsets will give you something odd and the other half something even. $\endgroup$ – G. Bach Oct 30 '14 at 22:04
  • $\begingroup$ That's not at all obvious, though @G.Bach, when the sum of all the cards is even. $\endgroup$ – Thomas Andrews Oct 31 '14 at 1:49
  • $\begingroup$ @ThomasAndrews: I don't quite understand your comment. In the example the sum of all cards is even. The symmetry exhibited here depends only on the presence of at least one card with an odd number. But it does seem like the comment by G. Bach is too naïve; one cannot say "due to symmetry" unless a concrete symmetry mapping has been indicated. $\endgroup$ – Marc van Leeuwen Oct 31 '14 at 8:53
7
$\begingroup$

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$.

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Of course, $\sum_{k=0}^{n/2}\binom{n}{2k} = 2^{n-1}$ might require proof. It is the heart of the question, really. $\endgroup$ – Thomas Andrews Oct 30 '14 at 13:45
  • $\begingroup$ @ThomasAndrews $\binom n0+\binom n2+\binom n4+..=\binom n1+\binom n3+\binom n5+...=\frac12(1+x)^n_{x=1}$ $\endgroup$ – RE60K Oct 30 '14 at 13:47
  • $\begingroup$ What does $(1+x)_{x=1}^n$ mean? The tradition proof is to compute $(1+(-1))^n$... $\endgroup$ – Thomas Andrews Oct 30 '14 at 13:50
  • $\begingroup$ that establishes the first equality but the sum of first two terms is the third term, @ThomasAndrews $\endgroup$ – RE60K Oct 30 '14 at 13:51
  • $\begingroup$ Ah, you mean $(1+x)^n$ evaluated at $x=1$. Was having a hard time parsing that. $\endgroup$ – Thomas Andrews Oct 30 '14 at 14:28
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ There are, however, an even number of odd cards, so your second bullet is wrong. $\endgroup$ – Thomas Andrews Oct 31 '14 at 2:00
  • $\begingroup$ Easily fixed. Who the hell downvotes this? I think it's quite an elegant proof. $\endgroup$ – smci Oct 31 '14 at 8:30
  • $\begingroup$ WWht is $U$? You need to prove this operation is $1-1$ and onto. #P is not $2^{n-1}-1$ because that is not how you defined #P. Basically, this answer is sloppy. $\endgroup$ – Thomas Andrews Oct 31 '14 at 13:13
  • $\begingroup$ Finally, you don't say when you choose which $P'$. $P'=\{15-p_i\}$ might or might not add up to an even number, but also might include zero, so it is not true that "Both are invalid..." $U\setminus P$ is yields a valid set in all cases, if $U=\{1,2,3,\dots,15\}$. $\endgroup$ – Thomas Andrews Oct 31 '14 at 13:17
  • $\begingroup$ Note "they change the number of odd cards" is actually false in both cases. $\{1,2,3,4\}\to\{15-1,15-2,15-3,15-4\}$ sends an even sum to an even sum. If $U=\{1,\dots,15\}$ then $U\setminus P$ is always the same sum parity, since the sum of the values in $U$ is even. (This transformation would work if there were an odd number of odd elements in $U$, which is why just fixing that bullet did not fix your answer.) $\endgroup$ – Thomas Andrews Oct 31 '14 at 13:27

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.