Câu hỏi 67
Các thí sinh của kỳ thi MMO năm nay được xếp "tốt" vào $n$ cột (một cách xếp vào các cột là "tốt" nếu không có hai thí sinh nào trong cùng một cột quen biết nhau), nhưng không thể xếp được như vậy vào ít hơn $n$ cột. Chứng minh rằng tồn tại các thí sinh $M_1, M_2, \dots, M_n$ sao cho các điều kiện sau thỏa mãn:
(1) $M_i$ nằm ở cột thứ $i$, với mỗi $i=1,2,\dots,n$;
(2) $M_i$ và $M_{i+1}$ quen biết nhau, với mỗi $i=1,2,\dots,n-1$.
(1) $M_i$ nằm ở cột thứ $i$, với mỗi $i=1,2,\dots,n$;
(2) $M_i$ và $M_{i+1}$ quen biết nhau, với mỗi $i=1,2,\dots,n-1$.