Find the probability that an integer selected between 1 and 5000 is divisible by at least one of 3, 5 and 7

Question

I'm having a hard time finding the solution. I can find integers that are divisible by only one of them, but there are many that are divisible by two of them. That's the problem. Find the probability that an integer selected between 1 and 5000(inclusive) is divisible by at least one of 3, 5,7, but not divisible by all of these numbers.

Answer 1

Hints:

There are a total of $\lfloor\frac{n}{k}\rfloor$ numbers divisible by $k$ in the set of numbers $\{1,2,\dots,n\}$

The principle of inclusion-exclusion states as a special case that $|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$.

Let $A=\{\text{numbers in 1,2,...,5000 divisible by}~3\}$, $B=\{\text{numbers in 1,2,...,5000 divisible by}~5\}$, etc... then what does $A\cap B$ represent, and what does $A\cap B\cap C$ represent? How to find $|A|,|A\cap B|, |A\cap B\cap C|$?

Answer 2

As pointed out by JMoravitz comment, you will have to use the principle of inclusion-exclusion.

I will assume you were able to calculate the probability $P_3$ of selecting an integer divisible by 3, and analogously for $P_5$ and $P_7$.

Now, we can't just say that the answer of the question is $P = P_3 + P_5 + P_7$, because, for example, the number 35 was counted twice. The key here (principle of inclusion-exclusion), is to note that all numbers divisible by 35 were counted twice; the same is true for the numbers divisible by 15 and 21. Therefore, we just adjust our calculation to fix that.

Our new guess would be $P = P_3 + P_5 + P_7 - P_{15} - P_{21} - P_{35}$, but as you can see there is still something wrong: the number 105 was at first counted three times (one in $P_3$, one in $P_5$ and one in $P_7$), but now we subtracted it's participation three times (one in $P_{15}$, one in $P_{21}$ and one in $P_{35}$) - which means our new guess for the answer didn't count numbers like 105 at all. We must again adjust our response to

$$P = P_3 + P_5 + P_7 - P_{15} - P_{21} - P_{35} + P_{105}$$

Getting to the final answer. I leave to you to double-check this answer and ensure it is correct, i.e., it didn't count any number more times than it should, or less times than it should. Also, I will leave to you the calculation of each $P_i$, which shouldn't be hard, as you stated that you didn't have problem calculating $P_3$, $P_5$ and $P_7$.

---

EDIT: Thanks JMoravitz for pointing out - my answer is for the question in your title, but I missed the extra condition in the end of your question: "but not divisible by all". You'll have to adjust my solution to fit that condition. That is not that hard though, I'll leave that part for you as well. If you still experience problems, though, feel free to comment and I will gladly help you further.