Induction question about partitioning with a condition

Question

We have $n$ students which are in $k$ classes. We know that between each two classes, there exist two persons A and B who know each other. Prove that we can put students in $n-k+1$ groups such that all the persons in a group know each other. (the proof is probably with induction)

I don't know how should I approach this question. Should I use induction on $n$ or $k$? how?

P.S:

I found a question similar to this in math.se ... question link

I think this is the same question although the mentioned question has one more condition. (No person in a class know each other!) but unfortunately it seems the inductive answer of that question is somehow incomplete.

Answer 1

I will tell you how far I was able to go with the information you provided.

There are $n$ studentes and $k$ classes. For each pair of classes, two students know each other. There are $\binom{k}{2}$ pairs of classes, therefore there are $2\binom{k}{2}$ students that know each other, i.e. two students for each pair of classes.

Note that $2\binom{k}{2}=\frac{k!}{(k-2)!}$, so that there are at least $\frac{k!}{(2-k)!}$ students that know each other. I say at least because here is where the lack of info comes into place! Can a student $A$ know more than one other student $B$ from another class, or does each student know only one other student $B$ from another class? This is a key question.

Also, do the $k$ classes contain an equal amount of students? In other words, are students distributed evenly among the classes? This type of information is important when it comes to solve the problem.

You'll see if this points aren't clarified how can we know we are not finding any contradictions? For example, if students aren't evenly distributed we could have empty classes where there's no $A$ that knows any $B$; this would affect calculation. If they are distributed evenly, there are pairs of values for $n$, $k$ that don't work; for example, you can't evenly distribute $n=5$ students on $k=3$ classes; a class will always be with one student less. In few words the lesson is: give more info! More info means more help.

Answer 2

The proof is by induction on $k$, the result being obvious when $k=1$.

Call one of the classes "graph theory," and let the graph theory class have $m$ students. The remaining $n-m$ students in the other $k-1$ classes can be partitioned into $t:= n-m-(k-1)+1$ groups. Call these groups $S_1,S_2,\dots,S_t$. Let $s_i$ be the number of people in $S_i$ who are friends with someone in the graph theory class.

I claim that there exists an $i$ for which $s_i=|S_i|$. If not, we would have $$ \sum_{i=1}^t s_i\le \sum_{i=1}^t(|S_i|-1)=\left(\sum_{i=1}^t S_i\right) -t=(n-m)-t=n-m-(n-m-k+2)=k-2 $$ But this contradicts the fact that the graph theory students know $k-1$ students in the other classes in total.

Now, choose some particular $i$ for which $s_i=|S_i|$. This means that everyone in $S_i$ is friends with someone in the graph theory class. Let $G=\{g_1,g_2,\dots,g_j\}$ be set of graph theory students who are friends with someone in $S_i$. For each $h\in \{1,2,\dots,j\}$, let $F_h$ be the set of students in $S_i$ that $g_h$ is friends with. This means the sets $F_1,F_2,\dots,F_j$ are a partition of $S_i$.

The solution is this: everyone in the graph theory class is in a group by themselves, an everyone else is in their original grouping, except for the people in $G\cup S_i$. The group $S_i$ is disbanded, and all of the groups $$\{g_1\}\cup F_1,\{g_2\}\cup F_2,\dots,\{g_j\}\cup F_j$$ are formed. Now, let us count the number of groups:

• There are $t-1$ groups of the form $S_1,S_2,\dots,S_{i-1},S_{i+1},\dots,S_t$.

• There are $m-j$ singleton groups, consisting of the graph theory students who are not in $G$.

• There are $j$ groups of the form $F_1,F_2,\dots,F_j$.

Therefore, the number of groups is $(t-1)+(m-j)+j=n-k+1$, as required.