What is the probability that an integer in the set is divisible by and not divisible by ?
- A)
- B)
- C)
- D)
- E)
Answer
C
Key insight
Count the 50 even numbers, then take away the even numbers that are also multiples of 3, which are the 16 multiples of 6. That leaves 34.
Solution
Start with all the even numbers, then remove the ones that are also multiples of .
1. Even numbers from to : . There are of them.
2. An even number that is also a multiple of is a multiple of . Those are . Since and is too big, there are of them.
3. Even numbers that are not multiples of : .
4. The probability is
The answer is .
Why this works
"Divisible by but not by " means: take the multiples of , then throw out the ones that are multiples of both, which are the multiples of . The count of multiples of up to must be a whole number, , so the answer is not exactly one third of the evens. Whenever the upper limit is not a multiple of the step, count carefully instead of using a fraction.
The trap
Assuming exactly one third of the even numbers are multiples of 3 and answering 1/3, but 100 is not a multiple of 6, so the count is 16, not 16 and two thirds.
Concise solution
Multiples of up to : .
Among these, the ones also divisible by are the multiples of : (namely ).
Even numbers that are not multiples of : . The probability is .
The answer is .
Review in the AoPS books
- Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
- Introduction to Counting & Probability, Chapter 7: Introduction to Probability
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
- Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)
Techniques
Count the complement and subtract from the total