How many six-digit numbers are divisible by at least one of the numbers 24, 18? How many of them are divisible by exactly one of them?

Question

I wrote a code that counts the number of these numbers and found out that the answer to the first question is 75000 and the answer to the second question is 62500. I also realised that I need to use an inclusion and exclusion formula to calculate this. But I hadn't used it before, so it was hard for me to write it correctly

Answer 1

Right. So the first part is asking you how many six-digit multiples of either $24$ or $18$ (or both) there are. Let's begin by finding the number of six-digit numbers divisible by $24$. It so happens that the smallest such number is $100008$, which is equal to $4167\times24$. The largest such number is $999984$, and it is equal to $41666\times24$. There are therefore $41666-(4167-1)=37500$ six-digit numbers divisible by $24$.

Now for divisibility by $18$: $100008$ is the smallest such number, equal to $5556\times18$. The largest such number is $999990=55555\times18$. There are therefore $55555-(5556-1)=50000$ six-digit numbers divisible by $18$.

Now if we call the first set of numbers $A$ and the second set $B$, with $|A|=37500$ and $|B|=50000$, the first part of the question is asking you to find $|A\cup B|$. You might think this is equal to $|A|+|B|$, but this would be double-counting the numbers divisible by $24$ and $18$. This is where the inclusion-exclusion principle comes into play: it states that $|A\cup B|=|A|+|B|-|A\cap B|$ — in other words, the sum of the number of numbers divisible by $24$ and $18$, minus the number of numbers divisible by both. So let's work that last quantity out.

The least common multiple of $24$ and $18$ is $72$; in other words, the six-digit multiples of $72$ are precisely those which are multiples of $24$ and $18$ at the same time. The smallest such six-digit number is $100008=1389\times72$. The largest such number is $999936=13888\times72$. There are therefore $13888-(1389-1)=12500$ six-digit numbers divisible by $72$.

We now have everything we need. We want $|A\cup B|$, and by the inclusion-exclusion principle this is equal to $|A|+|B|-|A\cap B|$. Substituting the proper values, we get $|A\cup B|=37500+50000-12500=75000$, which matches the given answer.

Now for the second part of the question. This is basically asking for the same quantity as the first part, except that the multiples of $72$ aren't included at all, i.e. we want the number of six-digit numbers divisible by $24$ or $18$ but not both; it is a case of the "exclusive or". In short, it is asking for $|A\cup B|-|A\cap B|$. Again, substituting the proper values, we get that it is equal to $75000-12500=62500$, which again matches the correct answer and so we are done.