Question 1Level 2 · ExamSingle correct
Let A={1,2,3,4}. How many relations R on A (that is, subsets R⊆A×A) are reflexive and symmetric but **not** transitive? Exactly one option is correct.
Show answer and solution
Answer: B
A reflexive relation contains all four pairs (a,a). A symmetric relation contains (a,b) exactly when it contains (b,a). So a reflexive symmetric relation on A is fixed by choosing which of the (24)=6 unordered pairs {a,b} with a=b are included. That gives 26=64 such relations.
A reflexive symmetric relation is transitive exactly when it is an equivalence relation. Equivalence relations on a 4-element set correspond to partitions. The partition types are 4 (1 way), 3+1 (4 ways), 2+2 (3 ways), 2+1+1 (6 ways) and 1+1+1+1 (1 way). That gives B4=15 partitions.
Required number =64−15=49.
Difficulty: HardQuestion 2Level 3 · AdvancedOne or more correct
For an integer k, define the relation Rk on Z by aRkb if and only if 12∣(a+kb). For relations R⊆X×Y and S⊆Y×Z, the composition is S∘R={(x,z):there is y with (x,y)∈R and (y,z)∈S}, and the inverse is R−1={(y,x):(x,y)∈R}. Which of the following statements is (are) correct? One or more options may be correct.
ARk is symmetric for exactly 33 values of k∈{1,2,…,100}
BR5 is transitive
CR5∘R5={(a,c)∈Z×Z:12∣(a−c)}
DRk is an equivalence relation for exactly 8 values of k∈{1,2,…,100}
Show answer and solution
Answer: A, C, D
Symmetry. Suppose Rk is symmetric. Take b=1, a=−k; then (a,b)∈Rk, so (b,a)∈Rk, which means 12∣1−k2.
Conversely, if k2≡1(mod12) and a≡−kb, then b+ka≡b−k2b≡0. So Rk is symmetric ⟺k2≡1(mod12)⟺k≡1,5,7,11(mod12)⟺gcd(k,6)=1.
In {1,…,100} there are 100−50−33+16=33 such k. So (A) is correct.
Reflexivity needs 12∣(1+k)a for all a, which means k≡11(mod12). Then a+kb≡a−b, and Rk is congruence mod 12, which is an equivalence relation. Hence Rk is an equivalence relation ⟺k≡11(mod12). The values are k=11,23,…,95, so 8 values, and (D) is correct.
(B) Counterexample: (7,1)∈R5 since 12∣12, and (1,7)∈R5 since 12∣36, but (7,7)∈/R5 since 12∤42. So R5 is not transitive, and (B) is wrong.
(C) (a,c)∈R5∘R5 if and only if some b has 12∣a+5b and 12∣b+5c. Then b≡−5c and a≡−5b≡25c≡c. Conversely, if a≡c, take b=−5c. So R5∘R5={(a,c):12∣(a−c)}, and (C) is correct.
Difficulty: Peak challengeQuestion 3Level 3 · AdvancedNumerical answer
Let A={1,2,…,20} and R={(a,b)∈A×A:ab is a perfect square}. Find the number of elements of R. Give the answer as an integer.
Show answer and solution
Answer: 42
Write each m as m=s(m)k2 with s(m) squarefree, the squarefree part of m. Then ab is a perfect square ⟺s(a)=s(b).
Proof: ab=s(a)s(b)(kl)2 is a square exactly when s(a)s(b) is a square. A product of two squarefree numbers is a square only when they are equal.
So R is an equivalence relation whose classes are grouped by squarefree part:
s=1:{1,4,9,16}, s=2:{2,8,18}, s=3:{3,12}, s=5:{5,20}, and singletons for s=6,7,10,11,13,14,15,17,19 (9 classes).
∣R∣=∑(size)2=16+9+4+4+9=42.
Difficulty: Very hard