Problem
In a class there are 3n students. For a student x, let d(x) denote the number of friends of x in the class*. Suppose that
(1) the maximum value of d(x) is 4;
(2) if x is a friend of y, then d(x)+d(y)<7;
(3) no four students are friends of each other;
(4) no three students have three other common friends**.
Show that we can split the 3n students into 3 classes (say, A, B, C) of n students such that no friends are in the same class.
* If x is a friend of y, then y is a friend of x.
** This means there do not exist distinct a, b, c, x, y, z such that x, y, z are all friends of a, b, c.
Solution
(0) Assume the statement is false. Consider a counterexample with the smallest n.
By (1), assume a student v has friends w1, w2, w3 and w4.
By (2), each of w1, w2, w3 and w4 has at most one friend other than v, and call them u1, u2, u3 and u4 (if exist). We shall divide all possibilities into four cases, and show that in each case we can split the students as desired.
Case 1: Some u (say, u1) does not existFirst ignore v, w1 and w2. By (0), the remaining 3(n-1) students can be split into 3 classes of n-1 students each. Then
- put v into a class (say, A) to which w3 and w4 do not belong;
- put w1 and w2 into classes B and C respectively.
Case 2: All u's exist, but some u and w are equal (say u1=w2)Same proof as Case 1
Case 3: All u's exist and no u and w are equal, but some u's are equal (say u1=u2)First ignore v, w1, w2, w3, w4 and u1. By (0), the remaining 3(n-2) students can be split into 3 classes of n-2 students each. Then
- put v and u1 into some class (say A) so that u1 (who has at most 2 friends other than w1 and w2) does not meet his friends;
- put w3 (who has at most 1 friend other than v) into some class other than A (say B) so that he does not meet his friends, and put w1 into the remaining class (C in this case);
- repeat the above process for w4 and w2.
Case 4: All u's exist and are distinct, and no u and w are equalFirst ignore v, and temporarily regard w1 and w2 as one single student y1 (with friends u1 and u2), and w3 and w4 as one single student y2 (with friends u3 and u4). By (0), the resulting 3(n-1) students can be split into 3 classes of n-1 students each. Then
- in case y1 and y2 are in different classes (say A and B respectively), put w1 and w2 into class A, w3 and w4 into class B, and v into the remaining class (C in this case);
- in case y1 and y2 are in the same class (say A), put w1, w2 and w3 into class A, w4 into a class other than A to which u4 does not belong (say B), and v into the remaining class (C in this case).
Hence in each case we get a desired splitting, in contrary to (0). This completes the proof.
Reflections
Although not explicit, the above proof essentially makes use of the principle of mathematical induction, relying on smaller cases to prove a general case. This is one of the vast number of examples which show that mathematical induction can be a very powerful tool which can prove a huge variety of statements, other than the few typical examples in textbooks.
It is also worth to take note of the conditions given. It seems that the conditions (3) and (4) are never used in the proof. However, both of them are necessary conditions, as can be seen by the following examples:
- Suppose there are 6 students (i.e. n=2) a, b, c, d, e, f with a, b, c, d being friends of each other and e, f being friends of each other. This satisfies (1), (2), (4) but not (3), and the statement does not hold.
- Suppose there are 3 male students a, b, c and 3 female students x, y, z (i.e. n=2) such that two students are friends if and only if they are of opposite gender. This satisfies (1), (2), (3) but not (4), and the statement does not hold.
So why can a proof avoid making use of conditions that are necessary?
