Confirming your payment

Skip to content

Competency-Based Questions (CBQ) · Question 74 of 80

Let A be the set of all students in a school, and let R be the relation on A given by (a,b) R if and only if a and b…

Question 744 marksHard

Let AA be the set of all students in a school, and let RR be the relation on AA given by (a,b)∈R(a,b)\in R if and only if aa and bb study in the same class. Write A/RA/R for the set of all equivalence classes of RR. Every student belongs to exactly one class. For two classes XX and YY, write (X,Y)∈S(X,Y)\in S when some student of class XX has a sibling who studies in a different class YY. Throughout, no student has more than one sibling in the school.

Attempt any four of the following five sub-questions.

(a) Prove that RR is an equivalence relation on the set AA of students, and say what the elements of A/RA/R are in terms of the school.

(b) The school has 500500 students with 5050 in each class. Find ∣A/R∣|A/R|. Then show that the map π:A→A/R\pi:A\to A/R sending each student to their own class is onto but not one-one.

(c) Prove that SS is always symmetric, and that (X,X)∉S(X,X)\notin S for every class XX. Deduce that if SS is non-empty then SS cannot be transitive.

(d) Suppose instead that the 500500 students are spread over 2020 classes of 2525. Find the largest possible value of ∣S∣|S|, and describe an arrangement of siblings that attains it.

(e) Still with 2020 classes, find the least number of students a class must contain for the largest value in (d) to be attainable at all. Deduce that a school of 2020 classes of 1818 students could not reach that value, whatever its sibling arrangement. Finally, back in the school of part (d), find the greatest possible number of students who have no sibling when ∣S∣|S| attains its largest value.