Bài toán “nhóm 6 người” là gì?

Trong một cuộc thi toán ở Hungary năm 1947 có bài toán như sau: chứng minh rằng trong một nhóm 6 người bất kỳ, ít nhất có 3 người từng bắt tay nhau hoặc ít nhất có 3 người chưa từng bắt tay nhau. Tháng 6 năm 1956, một tờ nguyệt san toán học của Mỹ đã biến mệnh đề này thành một trò chơi toán học, và từ đó nó thường được gọi là “bài toán nhóm 6 người”.

Làm thế nào để chứng minh mệnh đề này? Trước hết, ta có thể biểu diễn 6 người bằng 6 điểm A, B, C, D, E, F. Nếu hai người từng bắt tay nhau, nối hai điểm tương ứng bằng nét liền; nếu chưa từng bắt tay nhau, nối bằng nét đứt. Như vậy, quan hệ bắt tay và không bắt tay trong nhóm 6 người được biểu diễn thành một đồ thị.

Giữa 6 điểm có tất cả 15 cặp điểm, nên có 15 cạnh. Mỗi cạnh có thể là nét liền hoặc nét đứt, tương ứng với việc hai người đã bắt tay hoặc chưa bắt tay. Vì vậy, về mặt hình thức có rất nhiều tình huống khác nhau.

Bây giờ xét một người bất kỳ, chẳng hạn A. Trong 5 người còn lại, theo nguyên tắc ô kéo, hoặc A đã bắt tay với ít nhất 3 người, hoặc A chưa bắt tay với ít nhất 3 người. Trước hết xét trường hợp A đã bắt tay với 3 người, giả sử là B, C, D.

Nếu trong ba người B, C, D không có ai bắt tay nhau thì ta đã có 3 người chưa từng bắt tay nhau. Nếu trong ba người đó có ít nhất một cặp đã bắt tay nhau, ví dụ C và D, thì A, C, D là 3 người từng bắt tay nhau từng đôi một. Như vậy mệnh đề được chứng minh trong trường hợp thứ nhất.

Trường hợp thứ hai, A chưa từng bắt tay với ít nhất 3 người, giả sử cũng là B, C, D. Lập luận tương tự: nếu B, C, D có 3 người từng bắt tay nhau từng đôi một thì ta có nhóm 3 người đã bắt tay nhau; nếu không, sẽ tìm được 3 người chưa từng bắt tay nhau. Do đó, trong mọi nhóm 6 người bất kỳ, luôn có 3 người từng bắt tay nhau hoặc 3 người chưa từng bắt tay nhau.

Nếu số người ít hơn 6, kết luận này không còn luôn đúng. Có thể sắp xếp quan hệ trong nhóm 5 người sao cho không có 3 người nào đã bắt tay nhau từng đôi một, cũng không có 3 người nào hoàn toàn chưa bắt tay nhau. Vì vậy, số 6 là con số tối thiểu cho bài toán này.