Interesting Induction Question (1 Viewer)

[Mahan1]

I haven't posted for a long time, I decided to post another unique induction question:
Suppose there are n students in a school with k classes.If for every two classes there is at least one student from each class who are friend with each other, i.e for every class A and B there is one student from A called a and one student from B called b, such that a and b are friends. Prove we can form n-k+1 groups from all the students in the school such that every member of each group are friend with each other.

 

[Mahan1]

I thought to share the answer, or at least give a rough idea of how to go about the question.

We use induction on n. In the n+1 case, if the number of classes, k , is n+1 then then the statement follows trivially.
We need to consider the case where
in that case at least there are two students, a and b, in a same class.Treat both of them as one student, let say c, and when we say c is friend with d, we mean either a or b is friend with d. Now we can use our inductive hypothesis to prove the result.