A number is chosen at random from among the first positive integers, and a positive integer divisor of that number is then chosen at random. What is the probability that the chosen divisor is divisible by ?
- A)
- B)
- C)
- D)
- E)
Answer
B
Key insight
Only the 9 multiples of 11 can work, and for each, exactly half its divisors are multiples of 11 since 11 appears once.
Solution
A divisor divisible by can only come from a number that is itself divisible by . Among these are : nine numbers, each of the form with . Since , the factor appears exactly once in each.
For such a number , pair each divisor of with . The divisors of not divisible by are exactly the divisors of , and the divisors divisible by are exactly the numbers . The pairing is a perfect match, so exactly half of the divisors of are multiples of .
Therefore the probability is
The answer is .
Why this works
Two-stage random choices multiply: probability of a good first choice times the probability of success given it. The second factor looks like it depends on , but the pairing shows it is for every with exactly one factor of . Whenever a prime divides exactly once, half of 's divisors contain .
The trap
Answering 9/100 by forgetting the second random step, or computing the proportion of divisors as 1/11 rather than 1/2.
Common mistakes
- Answering 9/100 by forgetting the second random step, or computing the proportion of divisors as 1/11 rather than 1/2.
- Listing the divisors of all nine multiples individually and making an arithmetic slip; the pairing argument makes this unnecessary.
Techniques
Map the objects to something easier to count · Exploit symmetry to reduce work or pair up objects