On S = 1, 2, ..., 20, a relation R is defined by a R b if the product ab is a perfect square. R is an equivalence relation. The number of ordered pairs (a, b) in R is
Answer: (B) 42 Status: Verified (T1). Checked by code and independent solves on 2026-11-20.
- 13
- 42
- 60
- 20
Solution
- ab is a square exactly when a and b have the same square-free part, so the classes are the square-free parts.
- Classes: 1,4,9,16, 2,8,18, 3,12, 5,20 and nine singletons 6,7,10,11,13,14,15,17,19.
- Ordered pairs = sum of (class size)² = 16 + 9 + 4 + 4 + 9 = 42. The number 13 counts classes, not pairs.
Fast method
Pairs in an equivalence relation = sum of squares of class sizes: 16 + 9 + 4 + 4 + 9 x 1 = 42.
Expected time: about 170 seconds. Difficulty: hard.
Topic page: Relations and equivalence relations