How many positive integers less than $N$ are not divisible by $4$ or $6$ for some $N$?
Positive integers less than $N$ not divisible by $4$ or $6$
1
$\begingroup$
combinatorics
-
0Will, perhaps you should start by breaking it down into cases of N. What if N itself is divisble by 4? By 6? By lcm(4,6)? – 2012-11-15
-
1And to follow up on that point, what if you look at 1, 2, 3, _4_, 5, _6_, 7, _8_, 9, 10, 11, _12_, 13, 14, 15, _16_... – 2012-11-15
-
0I'm not sure :/ – 2012-11-15
-
01/4 of all numbers are divisible by 4, 1/6 of all numbers are divisible by 6, and 1/(lcm 4,6) = 1/12 of all numbers are divisible by 4 and 6... so given a random N, P(divisible by 4 or 6) = P(divisible by 4) + P(divisible by 6) - P(divisible by 12) = 3/12 + 2/12 - 1/12 = 4/12 = 1/3... – 2012-11-15
-
0So N -(1/12)N? Is that it? – 2012-11-15
-
0Well, think about it. N/12 is not even a natural number unless 12 | N. The "chance" of a random natural number being divisible by 4 or 6 is 1/3, so the chance of a random natural not being divisible by 4 or 6 is 1 - 1/3 = 2/3, but this still doesn't answer your question, because you have to break N down into cases and then see if you can combine any of the cases into fewer statements. What happens if N = 4k? N = 6k? N = 12k? What happens otherwise? I am sure there are more clever ways to do this, but this is the way I would. – 2012-11-15
-
0What do you mean here¿ – 2012-11-15
-
0What I mean is what happens for integers 1 - 12 "mirrors" what happens for integers afterwards, so you can consider integers modulo 12 at the very most. For example, for N = 5, we have 1, 2, 3 = 3 numbers. For N = 7 we have 1, 2, 3, 5 = 4 numbers. For N = 12, we have 1, 2, 3, 5, 7, 9, 10, 11 = 8 numbers. What do you think would be true about N = 5 + 12? what about N = 7 + 12? – 2012-11-15