2007 AMC 10A Problem 16

P16-20~3 minPrint

Basic Probability Number Properties Use an invariant, parity, or coloring argument

Integers $a, b, c,$ and $d$ , not necessarily distinct, are chosen independently and at random from 0 to 2007, inclusive. What is the probability that $ad-bc$ is even?

Show solution without answering

Key insight

Only odd and even matter. A product of two random numbers is odd just 1/4 of the time, and ad - bc is even when both products match.

Solution

Whether $ad - bc$ is even depends only on which numbers are odd and which are even. From $0$ to $2007$ there are $2008$ numbers, exactly half odd and half even. So each of $a, b, c, d$ is odd with chance $\frac12$ .

When is $ad$ odd? Only when $a$ and $d$ are both odd. Chance: $\frac12 \times \frac12 = \frac14$ . So $ad$ is even with chance $\frac34$ .
Same for $bc$ : odd with chance $\frac14$ , even with chance $\frac34$ . It uses different letters from $ad$ , so the two products do not affect each other.
When is $ad - bc$ even? Look at the four cases:

$ad$	$bc$	$ad - bc$
odd	odd	even
even	even	even
odd	even	odd
even	odd	odd

So it is even exactly when the two products are both odd or both even.
4. Add those two chances.
$\frac14 \times \frac14 + \frac34 \times \frac34 = \frac{1}{16} + \frac{9}{16} = \frac{10}{16} = \frac58.$

The answer is $\boxed{\textbf{(E)}\ \frac 58}$ .

Why this works

For questions about "even" or "odd", replace every number by just its type, odd or even. A huge range of numbers then shrinks to a few cases. The surprise here is that products are even much more often than odd, which pushes the answer above one half.

Alternative approach

Find the chance that $ad - bc$ is odd instead. That needs one product odd and the other even: $\frac14 \times \frac34 + \frac34 \times \frac14 = \frac{6}{16} = \frac38$ . So it is even with chance $1 - \frac38 = \frac58$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Only parity matters. The range $0$ to $2007$ contains $2008$ integers, half odd and half even, so each of $a, b, c, d$ is odd with probability $\frac12$ , independently.

A product is odd only when both factors are odd, so
$P(ad \text{ odd}) = \frac12 \cdot \frac12 = \frac14, \qquad P(ad \text{ even}) = \frac34,$
and the same for $bc$ . Since $ad$ and $bc$ involve disjoint sets of variables, they are independent.

$ad - bc$ is even exactly when $ad$ and $bc$ have the same parity:
$P = P(\text{both odd}) + P(\text{both even}) = \left(\frac14\right)^2 + \left(\frac34\right)^2 = \frac{1}{16} + \frac{9}{16} = \frac{10}{16} = \frac58.$

The answer is $\boxed{\textbf{(E)}\ \frac 58}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques
Introduction to Algebra, Chapter 20: Special Functions (§20.3)