1

My thoughts on doing this problem:

total numbers is 60100

so from the total I subtract the numbers divisible by 2, 3, 4, 5, and 6.

Yet my answer

60100-30050-20033-15025-12020-10016

is a negative number. How to solve this problem?

Jinzu
  • 819
  • 2
    All of the numbers divisible by $4$ are divisible by $2$. The numbers divisible by $6$ are also numbers divisible by both $2$ and $3$. So your far "over-counting" the numbers to subtract. – amWhy Oct 19 '13 at 18:06
  • Related: sieve of Eratosthenes. See how some numbers get crossed out several times. – Julien Oct 19 '13 at 18:09
  • No full solution, just a hint: You counted some of them twice in building the difference. Note that for example all the 15025 numbers that are divisible by 4 are divisible by 2, too, so you should skip counting those again within the 30050 numbers that are divisible by 2. Similar for 6 with 3 and 2. – cubic lettuce Oct 19 '13 at 18:09

3 Answers3

2

We need to consider the primes only.

The number of Numbers divisible by at least one of $2,3,5$ will be $$\left\lfloor\frac{60100}2\right\rfloor+\left\lfloor\frac{60100}3\right\rfloor+\left\lfloor\frac{60100}5\right\rfloor-\left\lfloor\frac{60100}{2\cdot3}\right\rfloor-\left\lfloor\frac{60100}{2\cdot5}\right\rfloor-\left\lfloor\frac{60100}{3\cdot5}\right\rfloor+\left\lfloor\frac{60100}{2\cdot3\cdot5}\right\rfloor$$

lab bhattacharjee
  • 274,582
  • 1
    It might be good to mumble the words "inclusion-exclusion" where if $A$ is the event "divisible by $2$", $B$ is the event "divisible by $3$", and $C$ is the event "divisible by $5$", then $N(A; \text{or}; B; \text{or}; C) = N(A) + N(B) + N(C) - N(A; \text{and}; B) - N(A; \text{and}; C) - N(B; \text{and}; C) + N(A; \text{and}; B; \text{and}; C)$ (since the event that a number is divisible by a number in ${2, 3, 4, 5, 6}$ is the same as the event that it is divisible by one of $2, 3, 5$). Anyway, +1. – user43208 Oct 19 '13 at 18:42
  • Yes this is the correct answer, we just now subtract this total from 60100. – Jinzu Oct 19 '13 at 18:43
  • @user43208, thanks for pointing out the term (http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html) – lab bhattacharjee Oct 19 '13 at 18:44
0

you have to add to that negative number the numbers divisible by (2*3), (2*4), (2*5), (2*6), (3*4), (3*5), (3*6), (4*5), (4*6) and (5*6) as you are subtracting them twice

and subtract again the numbers divisible by (2*3*4),(2*3*5)...(all combinations of 3 numbers) because you are adding them three times, hence is like if you had not subtracted none of them at the beggining

then add all combinations of 4

and finally subtract (2*3*4*5*6)

user96233
  • 955
0

Firstly, as pointed out by others, you need only eliminate numbers divisible by $2,3,5$

How many numbers between $1$ and $30$ are indivisible by these numbers?

If you add $30$ to such an indivisible number, does its indivisible status change?

How many sets of $30$ numbers are there between $1$ and $60090$?

Can you check the numbers from $60091$ to $60100$ by hand?

DJohnM
  • 3,580