P and C – Fundamental Principle of Counting – 22 January 2025 (Shift 1)

Solution:

We need to find the number of fractions $\frac{m}{n}$ such that $m < n$, $m, n \in \{1, \dots, 10\}$ and they are coprime ($\gcd(m, n)=1$).

We iterate through possible values of denominator $n$:

• $n=2$: $\frac{1}{2}$ (1 value)
• $n=3$: $\frac{1}{3}, \frac{2}{3}$ (2 values)
• $n=4$: $\frac{1}{4}, \frac{3}{4}$ (2 values) [$\frac{2}{4}$ is not coprime]
• $n=5$: $\frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}$ (4 values)
• $n=6$: $\frac{1}{6}, \frac{5}{6}$ (2 values) [2,3,4 share factors with 6]
• $n=7$: $\frac{1}{7}, \dots, \frac{6}{7}$ (6 values)
• $n=8$: $\frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}$ (4 values)
• $n=9$: $\frac{1}{9}, \frac{2}{9}, \frac{4}{9}, \frac{5}{9}, \frac{7}{9}, \frac{8}{9}$ (6 values)
• $n=10$: $\frac{1}{10}, \frac{3}{10}, \frac{7}{10}, \frac{9}{10}$ (4 values)

Total number of elements $n(B) = 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31$.

Ans. (1)