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.
4

Cô nàng siêu robot Sophia từng tuyên bố “sẽ hủy diệt loài người” bây giờ ra sao?

Trong thời điểm AI bùng nổ, lời nói năm xưa của Sophia có đáng lo sợ?
5

Ảnh địa phận 29 tỉnh thành chỉ còn trong kỷ niệm, chạm cảm xúc nhiều người

Từ năm 2020 tới nay, anh Duy An rong ruổi tới khắp các vùng miền trên Tổ quốc, ghi lại bức ảnh về địa phận từng tỉnh thành. Không ngờ bộ ảnh nhận sự quan tâm đặc biệt do chạm tới cảm xúc nhiều người.

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.

Sức mạnh của người thấu cảm

Tủ sách - FN - 02/07/2025 09:00
Có bao giờ bạn phủ nhận cảm xúc của mình để làm hài lòng người khác, luôn nói “có” dẫu trong lòng muốn nói “không”, tự ép bản thân vào khuôn mẫu để không bị xem là khác biệt?

Oola – Tìm bình yên giữa vạn biến - Cuốn sách giúp bạn thoát khỏi vòng xoáy kiệt sức

Từ sách - Phim - Quìn - 02/07/2025 08:00
Mỗi đêm, dù đã gắng hết sức, bạn vẫn mang theo nỗi mệt mỏi và câu hỏi nhức nhối: “Mình đang sống vì điều gì?”. Áp lực, căng thẳng, cảm giác mất kết nối với chính mình âm thầm bào mòn bạn từng ngày, biến mọi nỗ lực thành cuộc chạy đua không có vạch đích.

12 nghệ sĩ hát trong MV "Rực rỡ ngày mới", truyền tải thông điệp nhân văn

Giải trí - Bích Phương - 01/07/2025 15:54
Mang giai điệu tươi sáng và thông điệp ý nghĩa, MV "Rực rỡ ngày mới" gây xúc động khi lan tỏa tinh thần nhân ái đến khán giả, bạn đọc nhân dịp kỷ niệm 20 năm thành lập báo điện tử Dân Trí.

Ảnh địa phận 29 tỉnh thành chỉ còn trong kỷ niệm, chạm cảm xúc nhiều người

Thư giãn - Việt Hà - 01/07/2025 13:19
Từ năm 2020 tới nay, anh Duy An rong ruổi tới khắp các vùng miền trên Tổ quốc, ghi lại bức ảnh về địa phận từng tỉnh thành. Không ngờ bộ ảnh nhận sự quan tâm đặc biệt do chạm tới cảm xúc nhiều người.

Xem Sex Education, tôi kinh ngạc trước 1 câu thoại quá hay, bèn đem đi dạy con trai

Điện ảnh - Thanh Hương - 01/07/2025 12:00
Khi nghe câu nói này, tôi đã bật cười và thích thú.

AI có thể tống tiền, phản bội khi cảm thấy bị đe dọa

Kỹ năng - Hoàng Vũ - 01/07/2025 11:00
Một nghiên cứu mới từ Anthropic cho thấy các mô hình ngôn ngữ tiên tiến như Claude hay Gemini không chỉ sẵn sàng vạch trần các vụ bê bối cá nhân để tự bảo vệ, mà thậm chí còn cân nhắc "để mặc bạn chết" nếu mục tiêu của chúng bị đe dọa.

Bức thư bà mẹ gửi con "nổi loạn": Nếu đứa trẻ nào cũng đọc được những câu chữ này, tương lai có thể sẽ khác

Suy ngẫm - Hiểu Đan - 01/07/2025 10:00
Tôi hy vọng nhiều bậc phụ huynh sẽ lan toả cho con mình chiêm nghiệm sớm!

Tôn thờ tuổi thơ "nghèo mà vui", cái giá phải trả đôi khi không chỉ là một kỳ thi trượt

Phong cách sống - Hiểu Đan - 01/07/2025 09:00
Cô gái trong sách "Em phải đến Harvard học kinh tế" lại một lần nữa khiến hội phụ huynh Việt "dậy sóng".

Bạn đang nghịch gì với đời mình - Khi khổ đau cũng là một phần của cuộc sống

Từ sách - Phim - Quìn - 01/07/2025 08:00
Có những ngày bạn cảm thấy mọi thứ từng bỗng vụn vỡ, những câu hỏi không lời đáp giày vò tâm trí: “Rốt cuộc mình sống để làm gì?”, “Tại sao phải đau khổ đến vậy?”. Bạn không biết bám vào đâu, càng vùng vẫy, càng thấy mình lún sâu trong một vũng lầy vô hình.

Tra cứu nhanh 168 phường, xã, đặc khu thuộc TP.HCM mới

Kỹ năng - 30/06/2025 13:55
Chuyên trang toàn cảnh thông tin về 168 phường, xã, đặc khu của TP.HCM chính thức đi vào hoạt động. Bạn có thể tra cứu, theo dõi video và các thông tin về hoạt động vận hành khi TP.HCM thực hiện chính quyền 2 cấp.

Cẩn thận với ký tự vô hình khi mở đường link trên điện thoại

Kỹ năng - Anh Tú - 30/06/2025 13:00
Chuyên gia bảo mật Gabriele Digregorio đã phát hiện một lỗ hổng tiềm ẩn trên hệ điều hành Android, có thể bị tin tặc khai thác để thực hiện các cuộc tấn công lừa đảo (phishing).

Xem 'Sex Education' tôi đau khổ hiểu ra: Dù hơn 30 tuổi vẫn mơ hồ về 2 chữ "trưởng thành"

Điện ảnh - Ứng Hà Chi - 30/06/2025 12:00
Hoá ra, trưởng thành không phải là kiểm soát mọi thứ, mà là học cách buông bỏ và bước tiếp.

Những lo ngại khi Facebook muốn truy cập vào thư viện ảnh trên điện thoại

Kỹ năng - Anh Tú - 30/06/2025 11:00
Facebook đang yêu cầu người dùng cho phép truy cập vào thư viện ảnh trên điện thoại để tự động đề xuất các phiên bản ảnh được chỉnh sửa bằng AI, gồm cả những bức ảnh chưa từng được tải lên Facebook.

Gia đình "độc lạ" Việt Nam, dâu rể các thế hệ mới đến đều choáng váng rồi... "nghiện" lúc nào không hay!

Phong cách sống - Khánh Huyền - 30/06/2025 10:00
Những ai lần đầu tiên đến gia đình tôi đều không giấu nổi sự sửng sốt. Có người khó tính từng bảo cách này khiến con cháu dễ sinh hư, thiếu tôn ti trật tự.

Khai mở hạnh phúc - Ba chiến lược giúp bạn hạnh phúc và viên mãn

Từ sách - Phim - Quang Thanh - 30/06/2025 09:00
Chúng ta thường nghĩ sức khỏe tinh thần suy kiệt là điều gì đó bất thường, thậm chí không tự nhiên. Nhưng bạn nên biết, có một số liệu thống kê nói rằng cứ bốn người sẽ có một người gặp những khó khăn về sức khỏe tinh thần.
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
Thứ 4, 02/07/2025