# How many unique pairs of integers between $1$ and $100$ (inclusive) have a sum that is even?

How many unique pairs of integers between $1$ and $100$ (inclusive) have a sum that is even? The solution I got was

$${100 \choose 1}{99 \choose 49}$$

I don't have a way to verify it, but I figured you pick one card from the 100, then you can pick 49 of the other cards (if the first card is even the other has to be even and if the first card is odd the other has to be odd as well).

-
Let $f(n)$ be the number of such pairs between $1$ and $n$. By making an explicit list, you can see whether your idea works for small $n$, like $2$, $3$, or $4$. – André Nicolas Dec 12 '11 at 9:59

This doesn't make much sense: $\binom{100}{1}\binom{99}{49}$ counts the number of ways of picking one out of 100 possibilities and 49 out of 99 possibilities. That is not what you want: you don't want to pick 49 other cards, you just want to pick one out of the 49 that are still "in play".

That is, I think what you meant was:

I can pick the first number arbitrarily, and there are $\binom{100}{1}$ ways of doing that; once I pick that, there are only $49$ other numbers that I can pick (those with the same parity as the one I picked), and that means $\binom{49}{1}$ of them. Multiplying we have $\binom{100}{1}\binom{49}{1}$.

(Note the $\binom{49}{1}$ rather than $\binom{99}{49}$).

That's almost right, but you are overcounting: you count the pair $(1,99)$ once when you first pick $1$ and then pick $99$; and you count it again when you first pick $99$ and then pick $1$. So, what's the easy way of taking care of that?

(To see that your answer cannot possibly be correct, note that there are only $$\binom{100}{2} = \frac{100(99)}{2} = 4950$$ pairs of numbers between $1$ and $100$; but $\binom{100}{1}\binom{99}{49} \approx 5\times 10^{30}$, which is way too many.)

-
Oh why thank you very much :) – Caleb Jares Dec 12 '11 at 6:58