A puzzle uses tiles numbered to . Two tiles and are called matching when the product is a perfect square. This defines a relation on :
is an equivalence relation on . How many equivalence classes does have, and what is the class ?
Confirming your payment
Competency-Based Questions (CBQ) · Question 44 of 80
A puzzle uses tiles numbered to . Two tiles and are called matching when the product is a perfect square. This defines a relation on :
is an equivalence relation on . How many equivalence classes does have, and what is the class ?
(A) classes;
(B) classes;
(C) classes;
(D) classes;
Option (D) is correct.
Step 1: the hidden label. Every positive integer can be written as , where has no square factor other than . Call the square-free part of . For example has , and has .
If and , then . This is a perfect square exactly when is a perfect square. Two square-free numbers multiply to a square only when they are equal. So
"Same label" is reflexive, symmetric and transitive, which is why is an equivalence relation, and each class is the set of tiles with one particular label.
Step 2: the class of . We need : give , and gives . Check: and . So
Step 3: count the classes. Sort all tiles by label:
| label | class |
|---|---|
| one tile each |
That is classes with more than one tile and single-tile classes: classes. As a check, the class sizes add up to .

Why the other options are wrong