"VẤN ĐỀ 6 NGƯỜI TỤ HỘI'' LÀ GÌ?
Năm 1947, trong đề bài của một cuộc thi toán học Olympic được tổ chức ở Hungary có một đề bài chứng minh sau: ''Chứng minh trong 6 người bất kỳ, ít nhất có 3 người từng bắt tay lẫn nhau hoặc ít nhất có 3 người chưa từng bắt tay nhau''. Tháng 6/1958, trong cuốn ''Nguyệt san toán học Mỹ'' nổi tiếng đã phát biểu lại câu hỏi được coi,như trò chơi toán học này. Từ đó nó trở thành câu đố vui nổi tiếng thế giới và được gọi là ''Vấn đề 6 người tụ hội''.
Chứng minh như thế nào đây? Trước tiên chúng ta có thể đặt 6 người tuỳ ý thành 6 điểm khác nhau trên một mặt phẳng với các ký tự tiếng Anh lần lượt là A, B, C, D, E, F đồng thời dùng đường nét liền nối giữa 2 điểm để biểu thị 2 người đã bắt tay nhau, dùng 2 đường đứt đoạn liên kết giữa 2 điểm để biểu thị 2 người chưa từng bắt tay. Như vậy, chúng ta có thể được một số hình vẽ biểu thị quan hệ bắt tay giữa 6 người. Từ hình 1 có thể thấy mệnh đề trên đều được thành lập.
Vậy có tất cả bao nhiêu hình vẽ như vậy? Trong hình vẽ quan hệ bắt tay, xuất phát từ mỗi điểm đều có thể vẽ ra đường thẳng với 5 điểm khác, tổng cộng có 6.5=30 đường, trong đó có một nửa là lặp lại, cho nên trong hình vẽ quan hệ bắt tay tổng cộng có 30:2=15 đường bên, mà mỗi đường bên đều có 2 khả năng là quan hệ bắt tay của 6 người tổng cộng có 215 trường hợp khác nhau. Dưới đây chúng ta sẽ chứng minh mệnh đề trên.
Trước tiên hãy xét trường hợp của một điểm trong đó, chẳng hạn là A, 5 người khác cần có ít nhất 3 người bắt tay với anh ta hoặc có ít nhất 3 người không bắt tay với anh ta, nếu không số người cùng anh ra bắt tay và không bắt tay cộng lại sẽ nhở hơn 5. Chúng ta xét trường hợp thứ nhất, A và ít nhất 3 người trong đó cùng bắt tay, giả sử 3 người đó là B, C, D. Nếu B, C, D không bắt tay lẫn nhau (hình 2), vậy thì kết luận có ít nhất 3 người không bắt tay trong mệnh đề được thành lập: Ngược lại trong 3 người có ít nhất 2 người bắt tay, chẳng hạn là C và D (hình 3), vậy thì kết luận có ít nhất 3 người đã bắt tay theo mệnh đề được thành lập. Chúng ta xét tiếp trường hợp 2, A và ít nhất 3 người trong đó chưa bắt tay nhau (ba người là B, C, D). Lúc này chỉ cần sửa đường nét đậm trong hình 2 thành đường nét đứt, cách chứng minh khác tương tự như trên, mọi người có thể tự minh thử, xem có được kết luận như thế nào.
Nói tóm lại chúng ta có thể chứng minh như sau: trong 6 người tuỳ ý, ít nhất có 3 người bắt tay lẫn nhau hoặc có ít nhất 3 người chưa bắt tay nhau.
Câu hỏi này còn có thể mở rộng hơn nữa: trong một tốp người không dưới 6 người có ít nhất 3 người từng bắt tay nhau hoặc có lt nhất 3 người chưa bắt tay nhau. Nhưng trong 5 người vừa không có 3 người bắt tay lẫn nhau, vừa không có 3 người chưa bắt tay lẫn nhau.
