3

In how many ways can you select two distinct integers from the set {1, 2, 3, . . . , 100} so that their sum is: (a) even? (b) odd?

I'm studying for a discrete midterm this coming Monday and saw the following problem on a practice midterm my Professor posted. I know the amount has to be less than C(100,2), but it would be naive to think the answer to a and b is just half that...right?

What's tricky about this problem is that I'm not confident about the relationship between odd and even numbers in generating sums. Here's what I can make out, at least intuitively:

Even + Even = Even, or C(50, 2) Odd + Odd = Even C(50,2) Even + Odd = Either (no idea how to compute this)

Am I approaching this problem the right way?

Chris T
  • 813
  • 2
    Even + Odd = Odd. – Exodd Jun 24 '16 at 17:52
  • Always? Well then that would simply things greatly, right? a) would be 2*C(50,2) and b would just be C(50,2). – Chris T Jun 24 '16 at 17:52
  • You're approaching the problem in the right way. Just think how to compute the last term. In how many ways you can pick an even number? and an odd number? – Exodd Jun 24 '16 at 17:53

2 Answers2

3

As noted in a comment, the sum of an even number and an even number is an odd number. Thus you've already solved the problem; just add up the two contributions you found for even sums and subtract them from the total number $\binom{100}2$ of sums. Alternatively, independently pick an even and an odd number, each in $50$ possible ways.

joriki
  • 238,052
  • I think you mean the sum of an even number and an odd number is an odd number, which is what Exodd said in the above comment. – Vaekor Jun 24 '16 at 18:00
  • I'm embarrassed to say this, but I may need a bit more help in unpacking this idea. Are you saying the total number of numbers that would sum to an odd number would be the two amounts I found for even numbers, summed, and then subtracted from C(100,2)? – Chris T Jun 24 '16 at 18:04
  • @ChrisT: Yes. You found three cases, two leading to even numbers and one leading to odd numbers. You correctly counted the cases leading to even numbers. Thus the rest must be the cases leading to odd numbers. Note also the alternative approach in the last sentence of the answer. – joriki Jun 24 '16 at 18:06
1

The solution $2 C(50,2)$ you gave in comments for part (a) is correct. For part (b), observe that the sum is odd iff one of the numbers is even and the other is odd. The even number can be chosen in $C(50,1)$ ways, and the odd number in $C(50,1)$ ways. So the answer for part (b) is $50^2$.

Ashwin Ganesan
  • 4,045
  • 11
  • 10