0
$\begingroup$

How many natural divisors of $8!$ are not divisible by any number from the group of the numbers $\{6,10,12,21\}$?

I am really thinking hard on this one but I'm just in my first steps in cominatorics =\

I tried the inclusion exclusion principle but something just not right in my answers. Can you explain that one?

Please hide the answer so i will have the chance to get it by my own.

$\endgroup$
5
  • 1
    $\begingroup$ Inclusion-exclusion is a good technique to use here. Also, note that any number that's divisible by 12 is also divisible by 6, and conversely any number that's not divisible by 6 is also not divisible by 12. So you could ask the same question with the set $\{ 6, 10, 21 \}$ and get the same result. $\endgroup$ – Michael Lugo Aug 28 '17 at 13:47
  • $\begingroup$ i try once again and got 25 as solution i think that its incorrect =\ $\endgroup$ – NedyLearing Aug 28 '17 at 14:17
  • 1
    $\begingroup$ You should edit the question to include your solution, so that we can see where you may have gone wrong. $\endgroup$ – Michael Lugo Aug 28 '17 at 14:22
  • $\begingroup$ Let $A$ to be the set of all natural numbers which divides at least one of the $6,10,12,21$ ; now use inclusion-exclusion principle to find $|A|$. $\endgroup$ – Davood KHAJEHPOUR Aug 28 '17 at 14:40
  • $\begingroup$ I try that S0= be the number of divisors of 8! (that 96) and then i created 3 statments A1 be the divisors of 6(that 16) A2 be the divisors of 10(that 9) A3 =be the divisors of 21 (that 4) and after the calc S0-S1+S2-S3 what i got was 25 =\ $\endgroup$ – NedyLearing Aug 28 '17 at 14:48
1
$\begingroup$

So, first step, establish the divisors of $8!$:

$8!=8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1 = 2^7\cdot 3^2\cdot 5\cdot 7$

Then there are $(7+1)(2+1)(1+1)(1+1) = 96$ factors in total.

We can find the count of numbers divisible by $6$, for example, by segregating $2\cdot 3$ from the decomposition above and counting factors in the remaining prime decomposition: $ 2^6\cdot 3\cdot 5\cdot 7$, giving $56$ factors divisible by $6$.

Similarly there are:
- $42$ factors divisible by $10$
- $32$ factors divisible by $21$
- $48$ factors divisible by $12$ (which are all also divisible by $6$, so we do not need to track these)

In the same way, we can find the count of factors that are divisible by both $6$ and $10$ - meaning they are divisible by $30$. These will be double-counted if we subtracted all the above values off the total factor count, so would need adding back in, and similarly for other pairings. Then this process would have wrongly added back the set divisible by all three factors under consideration, so that needs subtraction again to complete the inclusion-exclusion process.

  • $28$ factors divisible by $ \text{lcm}(6,10) = 30$
  • $28$ factors divisible by $ \text{lcm}(6,21) =42$
  • $14$ factors divisible by $ \text{lcm}(10,21) = 210 $
  • $14$ factors divisible by $ \text{lcm}(6,10,21) = 210 $ (the same as above of course)

Via an inclusion-exclusion process, we can thus determine the number of factors of $8!$ not divisible by any member of the given set:

$96 - (56+42+32) + (28+28+14) - 14 = \fbox{$22\,$}$

$\endgroup$
2
$\begingroup$

The answer is $22$. I tried to explain in the simplest way I could find: using sets.

Hope it can help

enter image description here

$\endgroup$
0
1
$\begingroup$

First, you can ignore $12$ because any number divisible by $12$ is already divisible by $6$. Your count of $96$ divisors of $8!$ is correct, but your count of those divisible by $6$ is not. You just need to count the divisors of $\frac {8!}6$. Once you subtract S1, S2, and S3, you have subtracted the numbers that are divisible by both $6$ and $10$ twice, once in S1 and once in S2, so you need to add them back in. That is where inclusion/exclusion comes in.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.