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

Trong cuộc thi Olympic toán quốc tế năm 1947 ở Hungari có một bài toán như sau: Chứng minh rằng trong một nhóm sáu người bất kì ít nhất có ba đã từng bắt tay nhau hoặc ít nhất có ba người chưa từng bắt tay nhau”. Tháng 6-1956 một tờ nguyệt san toán của Mỹ đã chuyển mệnh đề này thành một trò chơi toán học, từ đó hai bài toán trở thành một đề toán lí thú mà người ta thường gọi là “bài toán nhóm sáu người”.

Làm thế nào chứng minh mệnh đề đó? Trước hết ta có thể sắp xếp nhóm sáu người bất kì này trên sáu điểm đỉnh khác nhau và đại diện bằng các chữ cái A, B, C, D, E, F, dùng các nét liền để nối các đỉnh biểu diễn là người bắt tay nhau, và dùng nét đứt để biểu diễn việc hai người chưa hề bắt tay nhau. Nhờ đó ta biểu diễn được trạng thái bắt tay (và không bắt tay nhau) của nhóm sáu người thành giản đồ. Trên hình 1 mô tả trạng thái bắt tay của sáu người.

Theo như hình 1 có bao nhiêu trạng thái? Trong mỗi quan hệ bắt tay nhau, từ mỗi điểm đỉnh có thể vẽ 5 đường thẳng nối liền với các đỉnh khác tức là 6 x 5 = 30 cạnh, nhưng trong đó có một nửa là trùng nhau. Và như vậy trạng thái bắt tay nhau có 30: 2 = 15 cạnh, mỗi cạnh lại có hai loại nét liền và nét đứt và như vậy trong mối quan hệ bắt tay nhau của sáu người có 215 tình huống khác nhau. Dưới đây ta sẽ chứng minh luận đề nêu trên.

Trước hết ta xét một điểm đỉnh như A chẳng hạn ít nhất có thể bắt tay với ba người, và ít nhất cũng có ba người không bắt tay với A. Cũng tương tự ta sẽ tìm thấy trạng thái không bắt tay của A với ba người. Trước hết ta xét tình huống 1, ít nhất có ba người bắt tay với A.

Ví dụ B, C, D chẳng hạn. Như tình huống ở hình 2 biểu diễn ít nhất có ba người B, C, D chưa bắt tay với A (đường nối là nét đứt), nếu không số người bắt tay và không bắt tay nhau sẽ nhỏ hơn 5. Trước hết ta xét tình huống 1 trong trạng thái này. A ít nhất bắt tay với ba người ví dụ với B, C, D chẳng hạn. Nếu B, C, D là ba người chưa hề bắt tay nhau (hình 2) nên đây là tình huống có người chưa hề bắt tay nhau. Nếu không, trong ba người ít nhất có hai người bắt tay nhau, ví dụ giữa C và D (hình 3) như vậy đã đáp ứng với mệnh đề ít nhất có ba người bắt tay nhau. Ta hãy xét loại tình huống thứ hai, ít nhất A chưa hề bắt tay với ba người khác, giả sử với B, C, D; bấy giờ ta chỉ cần thay nét liền thành nét đứt trên hình 2. Các chứng minh tương tự, các bạn có thể tự tiếp tục và sẽ tìm được kết luận cần thiết. Từ các lí luận trên đây chúng ta có thể chứng minh, trong nhóm sáu người bất kì, ít nhất có ba người bắt tay nhau hoặc ít nhất có ba người chưa hề bắt tay nhau.

Người ta có thể tiến thêm một bước nữa, trong nhóm có sáu người ít nhất có ba người từng bắt tay nhau, hoặc ít nhất ba người chưa hề bắt tay nhau. Thế nhưng nếu số người ít hơn sáu thì kết luận sẽ không phù hợp. Hình 4 biểu diễn điều đó: trong nhóm sáu người không có ba người đã bắt tay nhau, cũng không có ba người chưa hề bắt tay nhau.

Vì sao không nên tắm nắng nhiều?

Ở một số nước Âu, Mĩ, nhiều người đặc biệt thích phơi mình ở bãi biển để tắm nắng. Các cô gái còn phơi cho da biến thành màu nâu, cho đó là đẹp.

Vì sao cá ngựa con được sinh ra từ bố?

Dưới đáy đại dương ấm áp, đặc biệt là ở vùng biển nông, luôn luôn sáng sủa rực rỡ. ở đó có nhiều loại thực vật dưới đáy biển, nhiều loại động vật bơi lội tung tăng với đủ loại màu sắc, hình dạng v.v..

Tại sao đeo dù giúp chúng ta hạ cánh an toàn?

Với các máy bay chiến đấu, khi bị trúng đạn, phi công bắt buộc phải tìm cách thoát khỏi máy bay. Nếu rơi từ độ cao hàng ngàn mét xuống đất, con người không tránh khỏi cái chết...

Tại sao mũ bảo hộ lao động phải làm theo hình bán cầu?

Các công nhân xây dựng hoặc công nhân hầm mỏ đều phải đội mũ bảo hộ khi làm việc. Mũ bảo hộ được làm theo hình bán cầu. Mũ bảo hiểm xe máy cũng có hình bán cầu...

Thế nào là hệ thống vận chuyển đường ống giao thông công cộng?

Hệ thống vận chuyển đường ống giao thông công cộng là một hình thức giao thông công cộng hoàn toàn mới, đặc điểm lớn nhất của nó là có thể vận chuyển...

Tại sao đánh rắn phải đánh "bảy tấc"?

Đương nhiên, không phải con rắn nào cũng đánh "3 tấc", "7 tấc", mà còn phải tuỳ thuộc vào sự khác biệt giữa chủng loài và kích cỡ.

Vì sao khí cacbonic trong không khí nhiều sẽ khiến Trái Đất nóng lên?

Bạn đã nhìn thấy phòng ấm xây dựng bằng kính chưa? Trong đó người ta trồng hoa. Ở nông thôn bạn cũng có thể thấy nông dân làm những ngôi nhà bao bọc...

Các hành tinh trong vũ trụ liệu có va vào nhau?

Nếu Trái Đất ở rất gần các hành tinh khác và chúng chuyển động ngược chiều nhau thì khả năng đụng độ rất dễ xảy ra. Nhưng thực tế, Trái Đất và các...

Vì sao thùng đựng dầu, phích đựng nước nóng đều có dạng hình trụ?

Thùng dầu, phích nước đều là các thùng, bình đựng chất lỏng. Bạn có chú ý các đồ đựng chất lỏng đều có dạng hình trụ, điều này có liên quan gì đến...