Math problem?

Question

Determine the number of ordered pairs, (p,q) so that p and q are chosen from the set {1, 3, 5, 7.........., 1999} and p>q.

Most thoroughly explained gets the 10. =)

Answer 1

First, how many elements are in the set. The answer is 1000 elements.

Say you picked the largest element ('1999') you would have 999 elements to pick for q that were smaller.

Say you picked the 2nd largest element ('1997') you would have 998 element to pick for q that were smaller.

See a pattern yet? Here it is summarized in a table:

If you picked '1999' you'd have 999 smaller elements
If you picked '1997' you'd have 998 smaller elements
If you picked '1995' you'd have 997 smaller elements
If you picked '1993' you'd have 996 smaller elements
...
If you picked '5' you'd have 2 smaller elements
If you picked '3' you'd have 1 smaller element
If you picked '1' you'd have 0 smaller elements

So really the question is what is the sum of the following?
0 + 1 + 2 + 3 + ... + 996 + 997 + 998 + 999

There is a well known formula for this of:
n (n + 1) / 2

999(1000) / 2
= 999,000 / 2
= 499,500

This formula comes from rearranging the sum as follows:
(0 + 999) + (1 + 998) + (2 + 997) + ... + (498 + 501) + (499 + 500).

Notice how each one adds up to 999. And there are 500 pairs.

500 x 999 = 499,500

That's how many pairs you could form where the first element is bigger than the second.

Another way to approach this is the think of putting all these numbers in a big hat. Now draw out one number. You have 1000 choices. Now pull out another number. Here you have 999 choices. This would be 999 x 1000 = 999,000. But only half of the combinations will have the right order of larger and smaller. Half the time you will get the wrong combination of a smaller number first, then a larger number. So divide by 2.

999,000 / 2 = 499,500.

Answer 2

number of elements in {1, 3, 5, 7, ........., 1999} is 1000.
number of ordered pairs (p, q) selected from this set where p>q
= 1 + 2 + 3 + 4 + 5 + 6 + 7 + ...........+ 999 = 999000