2007年11月21日 星期三

A mysterious induction

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 exist
First 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 equal
First 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?

3 則留言:

Polam 提到...
作者已經移除這則留言。
Polam 提到...

Kahoo,

If I have not misunderstood you, I don't see why the induction goes through in Case 1. After neglecting v, w1 and w2, why should condition (1) be satisfied by the remaining 3(n-1) people? In other words, why should the maximum of d still be attained when v is removed? Indeed if n = 2, then after neglecting the three chosen people, only 3 people are left and (1) could never be satisfied. Similar problems exist in the other cases. I don't see how to modify the proof though.

Kahoo 提到...

Polam,

You are right. In fact, (1) should be modified as

(1') d(x)<5 for every student x

But the result is correct; it can be shown that with (1) changed to

(1'') d(x)<4 for every student x

the statement holds. Making use of this result the proof in the article is therefore a proof of the statement with (1) changed to (1').