Tìm ra lời giải cho bài toán 'khách mời dự tiệc' thách thức cả thế kỷ với các nhà toán học

Anh Tú05/12/2023 13:00
Tìm ra lời giải cho bài toán 'khách mời dự tiệc' thách thức cả thế kỷ với các nhà toán học

Hai nhà toán học đã tìm ra cách mới để áp đặt trật tự cho sự hỗn loạn dưới dạng bài toán khách mời dự tiệc khiến họ bối rối trong gần một thế kỷ – được gọi là bài toán Ramsey, còn được viết là r(4,t).

Trong toán học, lý thuyết Ramsey đề cập tới “trật tự hỗn loạn”. Cho dù hệ thống lớn có phức tạp đến đâu thì trật tự vẫn sẽ nổi lên như một hệ thống con nhỏ hơn với cấu trúc độc đáo.

Con người từ khi có ý thức đã luôn tìm kiếm khuôn mẫu sống trong một thế giới hỗn loạn ngẫu nhiên. Chúng ta tìm kiếm trật tự trong mọi thứ, từ cuộc sống, thế giới xung quanh, đến Vũ trụ, và bạn có thể nói lý thuyết Ramsey giải thích khả năng chúng ta tìm thấy nó.

Số Ramsey có thể được coi là đại diện cho ranh giới của sự rối loạn. Và rất khó để tìm ra chúng. Kể từ khi nhà toán học Frank Ramsey chứng minh Định lý Ramsey vào cuối những năm 1920, cộng đồng toán đã có sự bối rối mà cuối cùng Sam Mattheus và Jacques Verstraete của Đại học California, San Diego đã giải được.

Verstraete nói: “Nhiều người đã nghĩ tới r(4,t) là một bài toán bỏ ngỏ trong hơn 90 năm qua. Chúng tôi thực sự đã mất nhiều năm để giải quyết. Và đã có nhiều lúc chúng tôi bế tắc và tự hỏi liệu mình có thể giải được hay không".

Một ví dụ phổ biến với lý thuyết Ramsey yêu cầu chúng ta tính xem cần mời bao nhiêu người đến một bữa tiệc sao cho có ít nhất ba người đã quen nhau hoặc ít nhất ba người sẽ hoàn toàn xa lạ với nhau.

Ở đây, số Ramsey (viết tắt r), là số lượng người tối thiểu cần có trong bữa tiệc để s người biết nhau hoặc t người không biết nhau. Điều này có thể được viết dưới dạng r(s,t) và chúng ta biết đáp án r(3,3) = 6.

Video Giáo sư toán học Trefor Bazett giải thích vì sao r(3,3) lại bằng 6

Verstraete nói "Đó là sự thật hiển nhiên và... tuyệt đối. Bất kể tình huống ra sao hay bạn chọn 6 người nào thì bạn sẽ có nhóm 3 người đều biết nhau hoặc 3 người không biết nhau. Bạn có thể tìm thấy nhiều hơn, nhưng bạn được đảm bảo rằng sẽ có ít nhất 3 người trong nhóm đều biết nhau hoặc nhóm không hề biết nhau".

Các bài toán Ramsey thường được giải bằng cách sử dụng đồ thị ngẫu nhiên. Ví dụ: với s được biểu thị là những điểm có các đường màu xanh lam ở giữa chúng và t là những điểm có các đường màu đỏ. Nếu biểu đồ đủ lớn, bạn sẽ tìm thấy trật tự, nhưng nó đủ phức tạp để làm bạn rối mắt như hình bên dưới.

ramseyproblemgraphilustration.jpg

Các nhà toán học đã chứng minh một định lý vào những năm 1930 mà sau này chỉ ra rằng đáp số của r(4, 4) là 18. Và kể từ năm 1995, chúng ta đã biết r(4,5) = 25. Chúng ta không chắc liệu việc 4 người quen bắt chuyện hay tập hợp 5 người lạ để trao đổi câu chuyện có ý nghĩa gì hay không. Nhưng nếu bạn mời 25 người đến dự một bữa tiệc, lý thuyết của Ramsey cho rằng bạn có thể chắc chắn rằng một trong điều trên sẽ xảy ra.

Bỏ chuyện tiệc tùng sang một bên, việc tìm số Ramsey cho một vấn đề về cơ bản giúp tìm ra ít yếu tố nhất mà một hệ thống cần có để đảm bảo chắc chắn về một thuộc tính nhất định. Nó rất hữu ích trong khoa học máy tính và toán học để cấu trúc mạng truyền thông và tạo ra các thuật toán phát hiện gian lận, cùng nhiều điều khác.

Verstraete giải thích: “Bởi vì những con số này nổi tiếng là khó tìm nên giới toán học tìm kiếm các ước tính”, đồng thời đặt vấn đề: “Vậy làm thế nào khi chúng ta không tìm thấy đáp án chính xác mà lại tìm ra ước tính tốt nhất cho những con số Ramsey này?”

Sau khi phát hiện ra các ước tính có thể được thắt chặt bằng cách sử dụng đồ thị giả ngẫu nhiên, Verstraete và nhà toán học Dhruv Mubayi của Đại học Illinois-Chicago đã giải thành công r(3,t) vào năm 2019.

Nhưng Verstraete gặp khó khăn trong việc tạo ra một đồ thị giả ngẫu nhiên cho r(4,t), vì vậy ông và Mattheus đã giải quyết vấn đề tồn tại lâu nay bằng cách kết hợp lĩnh vực hình học hữu hạn với lý thuyết đồ thị.

Với sự kết hợp đó, các nhà nghiên cứu đã ấn định s (những người quen biết lẫn nhau) là 4 và nghiên cứu số Ramsey khi t (người lạ) tăng lên. Sau gần 1 năm và vượt qua nhiều trở ngại về toán học, họ đã tìm thấy r(4,t) gần bằng hàm bậc ba của t. Đối với một bữa tiệc có 4 người đều biết nhau hoặc t những người không biết nhau, bạn cần mời bao nhiêu.

Như các nhà nghiên cứu tuyên bố, đây là ước tính tốt nhất. Nếu bạn quan tâm, kết quả của họ có thể được biểu diễn dưới dạng toán học như sau: r(4,t) = Ω(t^3/log4t ) khi t → ∞. 

Nhóm nghiên cứu tin rằng phương pháp của họ sẽ hữu ích cho các số Ramsey khác và có thể hỗ trợ việc ước tính các hàm toán học khác.

Verstraete nói: “Người ta không bao giờ nên bỏ cuộc, dù mất bao lâu đi chăng nữa. Nếu bạn thấy vấn đề đó khó khăn và bạn đang mắc kẹt thì nghĩa là đó là một vấn đề thú vị”.


Gửi bình luận
(0) Bình luận
1

Vì sao Kim Dung để cao thủ top 2 giới võ lâm bị Tạ Tốn dễ dàng hạ gục?

Cái chết của cao thủ này còn ẩn chứa nhiều bí mật.
3

Tại sao Tiểu Long Nữ và Vương Ngữ Yên có dung mạo giống nhau?

Tiểu Long Nữ và Vương Ngữ Yên sở hữu dung mạo giống nhau đến kinh ngạc.
4

Quán chè 16 món tồn tại hơn nửa thế kỷ ở TPHCM, mỗi ngày bán gần 1.000 chén

Khoảng 15h, quán "chè mâm 16 chén" tọa lạc ở chung cư Ngô Gia Tự (quận 10, TPHCM) lại tấp nập khách đến ăn. Những nồi chè to trong quán bốc khói nghi ngút, tỏa ra hương thơm hấp dẫn thực khách.
5

Kiếm hiệp Kim Dung: Mỹ nhân sở hữu võ công vô địch nhưng không xuất hiện trực tiếp

Trong thế giới kiếm hiệp Kim Dung, Lâm Triều Anh là một nhân vật đặc biệt, sở hữu võ công cái thế nhưng lại không trực tiếp xuất hiện trong cốt truyện chính.

Cao thủ đen đủi trong Thiên long bát bộ: Võ công sánh ngang Mộ Dung Phục, chết thảm dưới tay một phụ nữ

Cao thủ này từng được Kiều Phong (Tiêu Phong) nhận xét có nội lực ghê gớm.

Người ký họa các phiên tòa tại Mỹ

Trang Business Insider giới thiệu họa sĩ Jane Rosenberg – người có thâm niên hơn 40 năm vẽ tranh các phiên tòa tại Mỹ.

Các nhà khoa học mách cách vượt qua nỗi sợ loài nhện

Trong bài trước, ta đã biết số lượng nhện đang suy giảm đáng báo động mà loài người không hay. Lâu nay, chính chứng sợ nhện đã khiến con người bàng quan với động vật rất hữu ích này.

Số lượng nhện đang suy giảm đáng báo động mà loài người không hay biết

Nhà sinh vật học Pedro Cardoso thuộc Đại học Lisbon cho biết trên thực tế, trên toàn thế giới, tất cả các loại nhện dường như đang biến mất.

Động vật có khả năng nhận thức bản thân khi soi gương không?

Nghiên cứu về việc liệu động vật có thể nhận ra mình trong gương hay không bắt đầu được thực hiện từ năm 1970 và kể từ đó chỉ một số ít loài đã vượt qua bài kiểm tra.

Chuột có thể có trí tưởng tượng

Tạp chí khoa học Science ngày 2.11 vừa đăng tải một nghiên cứu phát hiện chuột có thể suy nghĩ về đồ vật và địa điểm không ở ngay trước mặt chúng.

Bí ẩn vụ trộm bộ não của thiên tài Albert Einstein

Chỉ vài giờ sau khi Einstein qua đời, bộ não của ông đã bị đánh cắp một cách đầy bí ẩn, "vụ trộm thế kỷ" kinh hoàng được che giấu hơn 3 thập kỷ.

Giấc mơ của cha ông ta ngày xưa nhân văn hơn con người thời nay

Một nghiên cứu được thực hiện bởi các nhà nghiên cứu từ Đại học Geneva (UNIGE) và Đại học Toronto tiết lộ rằng những giấc mơ của cha ông ta ngày xưa nhân văn hơn chúng ta ngày nay.

Tôi đọc người đọc mỗi ngày - Làm báo chân chính là cần đối thoại với người đọc mỗi ngày

Từ sách - Phim - Đan Thanh - 21/06/2025 14:00
"Tôi đọc người đọc mỗi ngày" là một câu chuyện nghề nghiệp, tinh lọc từ sổ tay biên tập của nhà báo Huỳnh Sơn Phước, sau 40 năm hành nghề tại báo Tuổi Trẻ.

Hàng chục nghìn webcam kết nối Internet đang vô tình 'phản chủ'

Kỹ năng - Anh Tú - 21/06/2025 13:00
Theo một nghiên cứu mới từ công ty an ninh mạng Bitsight, hơn 40.000 webcam trên toàn thế giới đang ở trong tình trạng có thể truy cập công khai qua Internet – thường là mà chủ nhân không hề hay biết.

Xem "Sex Education", tôi bẽ bàng nhận ra lý do con luôn quý bạn hơn quý mẹ

Điện ảnh - Mỹ Hạnh - 21/06/2025 12:00
Tôi cố hết sức để gần gũi, tâm sự với con. Nhưng đáp lại, con chỉ thích đi chơi với bạn.

Kiếm hiệp Kim Dung: Cao thủ duy nhất chết vì võ công do chính mình tạo ra

Thư giãn - Quốc Tiệp - 21/06/2025 11:00
Nhậm Ngã Hành là một nhân vật nổi bật trong tiểu thuyết Tiếu ngạo giang hồ của cố nhà văn Kim Dung, đã để lại dấu ấn sâu đậm trong lòng độc giả.

Gemini phát triển tính năng tóm tắt nội dung PDF trong Google Drive

Kỹ năng - Anh Tú - 21/06/2025 10:00
Google đang mở rộng khả năng của Gemini bằng cách sử dụng trợ lý AI này để tóm tắt nội dung PDF trong Google Drive. Đặc biệt là lần này, tính năng không chỉ đơn thuần dừng ở việc tạo bản tóm tắt.

Xuất hiện ‘người chuột chũi’ dưới lòng thành phố làm rúng động cõi mạng

Phong cách sống - Anh Dũng - 21/06/2025 09:00
Câu chuyện về người phụ nữ xuất hiện tại miêng cống thoát nước đã lan truyền khắp mạng xã hội thời gian qua. Đằng sau những hình ảnh không ngờ ấy lại là thực trạng đáng buồn của cả một cộng đồng dân cư.

Giáo dục đích thực của 'Hạnh phúc tuổi trẻ'

Từ sách - Phim - Hồ lam - 21/06/2025 08:00
Theo triết gia J. Krishnamurti, việc so sánh bản thân với người khác, với con người mình nên là, với ai đó may mắn hơn sẽ làm giảm giá trị, sai lệch quan điểm, bản sắc của mỗi cá nhân.

Chân dung kẻ "sống lỗi"

Suy ngẫm - S.A - 20/06/2025 13:00
Bạn luôn cảm thấy người khác làm sai với mình, nhưng đã bao giờ tự thấy mình đối xử với bản thân cũng không ra gì chưa?

Xem "Sex Education", tôi xấu hổ nhận ra chính mình đang đẩy con trai ra khỏi nhà

Điện ảnh - Mỹ Hạnh - 20/06/2025 12:00
Tôi luôn nghĩ rằng mọi thứ mình làm là vì tốt cho con. Bởi tôi quá yêu con mà thôi.

ChatGPT nâng cấp giọng nói, tạo cảm giác như trò chuyện với người thực

Kỹ năng - Anh Tú - 20/06/2025 11:00
OpenAI đã cải tiến chế độ giọng nói của ChatGPT, nhằm giúp người dùng có cảm giác như đang nói chuyện với một người thật.

Dịch vụ cho thuê "người lắng nghe không phán xét" nở rộ ở TP.HCM, Hà Nội

Phong cách sống - S.A - 20/06/2025 10:00
Người cung cấp dịch vụ chỉ nghe - không đưa ra phán xét, không tư vấn tâm lý. Người tìm đến chỉ cần trút sạch tâm sự, không sợ ai bàn tán chuyện của mình. Thế là 2 bên đều vui.

TP.HCM đóng Cổng Dịch vụ công

Kỹ năng - Q.Huy - 20/06/2025 09:28
Trung tâm Chuyển đổi số TPHCM vừa thông tin chính thức về việc đóng Cổng Dịch vụ công thành phố. Kể từ 21h ngày 18/6, Cổng Dịch vụ công trực tuyến TPHCM được đóng để hợp nhất với Cổng Dịch vụ công quốc gia từ ngày 19/6.

Cuộc đời rực rỡ của Gillian Lynne: Từ cô bé bị trường từ chối dạy trở thành vũ công huyền thoại

Truyền cảm hứng - Tiểu Ngạn - 20/06/2025 09:00
Gillian Lynne là minh chứng sống cho câu nói "Không gì là không thể" và câu chuyện cuộc đời bà đã thành nguồn cảm hứng cho nhiều bậc cha mẹ trong hành trình dạy dỗ con cái.

Bạn đang chăm sóc bản thân thật sự hay... tiêu tiền cho bớt mệt?

Từ sách - Phim - Quìn - 20/06/2025 08:00
"Chăm sóc bản thân" đang dần trở thành một lối sống thời thượng – với spa, shopping, và những trải nghiệm sang chảnh. Nhưng liệu tất cả những điều đó có thực sự giúp bạn chữa lành? Hay chỉ là cách để tạm thời làm dịu đi sự mệt mỏi từ bên trong?

OpenAI nâng cấp một loạt công cụ cho ChatGPT phục vụ doanh nghiệp

Kỹ năng - Anh Tú - 19/06/2025 13:00
Với nỗ lực ngày càng tập trung vào nhóm người dùng doanh nghiệp, OpenAI vừa công bố hàng loạt nâng cấp mới cho ChatGPT.
HẠT GIỐNG TÂM HỒN
2019 Bản quyền thuộc về hatgiongtamhon.com.vn. Phát triển bởi ONECMS
Chủ nhật, 22/06/2025