Back to Intermediate source practice
IntermediateHardTITA Source: LaTeX
Number System/Divisibility and Inclusion--Exclusion

Question

MCQ} The number of positive integers n600n \le 600 such that nn is divisible by exactly two of the three numbers 44, 66, and 99 is:

Options

A

1717

B

3434

C

5151

D

6767

Answer

(C) 5151.

Detailed solution

} Let A, B, Cdenotethesetsofmultiplesofdenote the sets of multiples of4, 6, 9inin{1,2,\ldots,600}$.

  • lcm(4,6)=12, lcm(4,9)=36, lcm(6,9)=18, lcm(4,6,9)=36.\mathrm{lcm}(4,6)=12,\ \mathrm{lcm}(4,9)=36,\ \mathrm{lcm}(6,9)=18,\ \mathrm{lcm}(4,6,9)=36.
  • AB=600/12=50, AC=600/36=16, BC=600/18=33, ABC=16.|A\cap B|=\lfloor 600/12\rfloor=50,\ |A\cap C|=\lfloor 600/36\rfloor=16,\ |B\cap C|=\lfloor 600/18\rfloor=33,\ |A\cap B\cap C|=16.

Count divisible by exactly two: pairsAiAj3ABC\sum_{\text{pairs}}|A_i\cap A_j| - 3|A\cap B\cap C|

$

=(50+16+33)-3\cdot 16 = 99 - 48 = 51.

$

Structural insight: Since lcm(4,9)=36=lcm(4,6,9)\mathrm{lcm}(4,9)=36=\mathrm{lcm}(4,6,9), every multiple of both 44 and 99 is automatically a multiple of 66. So the pair {4,9}\{4,9\} alone is impossible -- contributing 00. The actual count breaks as (5016)+0+(3316)=34+17=51.(50-16) + 0 + (33-16) = 34 + 17 = 51.

Why this is CAT-level: The trap is mechanical inclusion--exclusion without noticing the structural collapse lcm(4,9)=lcm(4,6,9)\mathrm{lcm}(4,9)=\mathrm{lcm}(4,6,9). Students who plug into a memorised formula get the right number (5151) accidentally; students who reason from structure get it confidently. Wrong option (B) 3434 is the count from the {4,6}\{4,6\} pair alone -- a natural partial answer.

Answer: (C) 5151.