# Induction question about partitioning with a condition

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.

• It is not obvious that induction would work: for example adding an extra person (or an extra class) would allow different patterns of knowledge to exist – Henry Apr 20 at 18:01
• Just stating what I can figure. maybe try dividing number of students to show a posdible group size distribution ? – Roddy MacPhee Apr 20 at 18:40
• Consider the complementary graph of the friendship graph of your students. Each of its vertices has degree $\leq n-k+1$. Hence, its chromatic number is $\leq n-k+1$ as well (by the greedy coloring argument). The color classes will be the groups. – darij grinberg Apr 21 at 7:37
• Oops, I meant to say that each vertex has degree $\leq n-k$, not $\leq n-k+1$. Then, the greedy coloring works perfectly. – darij grinberg Apr 21 at 15:40
• @darijgrinberg I don't completely understand your reasoning. We have $k$ classes. If we consider one person in a class, we don't actually know how many people he is related to. We know for each two class, there exist two friends (one in Class 1 and one in Class 2). but it doesn't mean any person has necessarily friends in another class. – amir na Apr 21 at 19:16

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.

• I think it is safe to assume that no class is empty. (Because maybe for n = 3 , k =10, we get a negative number!). But because the question didn't tell us anything about how they are distributed, I think we can't assume they are distributed evenly. The question is as exactly as I said but maybe it is incomplete or assumed something is obvious which isn't actually obvious. Did you find any condition that helps solving the question? – amir na Apr 21 at 6:24
• Please read the P.S. I added to the question. – amir na Apr 21 at 8:45

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.