Inclusion-Exclusion Principle

CAT 1993 Slot 1 · QA · Medium · QA

All CAT 1993 Slot 1 questionsMore QA questionsAll CAT QA

The number of positive integers not greater than 100100, which are not divisible by 22, 33 or 55 is

  1. A.

    26

  2. B.

    18

  3. C.

    31

  4. D.

    None

Answer

A

Explanation

Using inclusion-exclusion for N=100N=100: Number of multiples of 2, 3, or 5: N(2∪3∪5)=⌊100/2⌋+⌊100/3⌋+⌊100/5⌋−(⌊100/6⌋+⌊100/10⌋+⌊100/15⌋)+⌊100/30⌋N(2\cup 3\cup 5) = \lfloor 100/2 \rfloor + \lfloor 100/3 \rfloor + \lfloor 100/5 \rfloor - (\lfloor 100/6 \rfloor + \lfloor 100/10 \rfloor + \lfloor 100/15 \rfloor) + \lfloor 100/30 \rfloor =50+33+20−(16+10+6)+3=103−32+3=74= 50 + 33 + 20 - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74. Numbers not divisible by 2, 3, or 5 =100−74=26= 100 - 74 = 26.

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace