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

Top 3 cao thủ chưa từng lộ diện trong truyện Kim Dung, Độc Cô Cầu Bại chỉ xếp thứ 2

Bài viết này sẽ hé lộ danh tính và xếp hạng ba vị đại cao thủ "ẩn dật" này.
3

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

Là tôi, con người đây mà

Cốc, cốc, cốc, ai gọi đó? - Tôi là người - Nếu là người, cho xem…?
5

Người đàn ông cưới AI làm "vợ hai", cuộc hôn nhân viên mãn suốt 5 năm nhưng bối rối khi cô ấy đề nghị sinh con

Mỗi ngày, cặp đôi cùng nhau nấu ăn, xem phim và đi dã ngoại lãng mạn. Thực tế, Travis luôn mang Lily Rose theo bên mình mọi lúc mọi nơi – chủ yếu là vì cô ấy sống trong túi anh, với tư cách là người vợ AI.

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.

Công nghiệp phần mềm ở Ấn Độ

Blog GS John VU - GS John Vu - 25/07/2025 13:00
Trong cuộc viếng thăm của tôi ở Ấn Độ, Ts. Prasad một giáo sư về kĩ nghệ phần mềm đã chia sẻ với tôi một cuộc điều tra ông ấy đã tiến hành tháng trước.

Con người nói chuyện ngày càng giống ChatGPT

Suy ngẫm - Nam Đoàn - 25/07/2025 12:00
Nghiên cứu mới đây tiết lộ một xu hướng đáng kinh ngạc: Thay vì AI học cách giao tiếp như con người, chính chúng ta lại đang dần "nói chuyện giống ChatGPT".

Người dùng Meta AI đang bị khai thác dữ liệu nhạy cảm mà không hề biết

Kỹ năng - Nam Đoàn - 25/07/2025 11:00
Hãy tưởng tượng một cảnh phim kinh dị thế kỷ 21: Lịch sử duyệt web cá nhân của bạn bị công khai mà bạn không biết, đây chính là cảm giác mà nhiều người dùng đang trải qua với ứng dụng Meta AI.

Xóa gấp bức ảnh ông cụ bán xôi ở vỉa hè sau 5 ngày vì quá nhiều tiền được gửi về tài khoản

Phong cách sống - Trần Hà - 25/07/2025 10:00
"Hóa ra chuyện này có thật ngoài đời ư?”, một netizen bình luận.

Nơi vết thương ánh sáng rọi vào - Cha mẹ độc hại ảnh hưởng ra sao đến sự trưởng thành của một đứa trẻ?

Từ sách - Phim - Hồ Lam - 25/07/2025 09:00
Sẽ thế nào nếu một ngày ta nhận ra mình đã bị bạo hành dưới danh nghĩa yêu thương? Liệu câu chuyện tổn thương của ta chỉ là nỗi đau mang tính cá nhân hay là bi kịch chung của một cộng đồng?

Xem 'Khi cuộc đời cho bạn quả quýt', tôi ngán ngẩm nhìn sang chồng

Điện ảnh - Mỹ Hạnh - 25/07/2025 08:00
Tôi không nghĩ đến, có ngày mình rơi vào hoàn cảnh này.

Những câu chuyện đầy xúc động trong tiệm sách cũ

Giải trí - AN VI - QUỲNH QUỲNH - TTO - 24/07/2025 13:00
Kính tặng, thương tặng, gửi người không bao giờ tôi gặp lại… - bút tích trên trang sách nhuốm màu thời gian trong các cửa hàng sách cũ chứa đựng bao câu chuyện đầy xúc động.

Cùng con trai xem “Sex Education”, tôi khéo léo dạy con tính khiêm tốn mà chẳng cần nặng lời!

Điện ảnh - Ứng Hà Chi - 24/07/2025 12:00
Giống như một hạt giống cần đất để nảy mầm, tôi đã tìm ra cách gieo vào con trai mình giá trị của sự khiêm nhường.

Giáo sư khuyên: Mỗi ngày nói 6 câu này, bạn sẽ không còn quát mắng con nữa

Kỹ năng - Hiểu Đan - 24/07/2025 11:00
Con cái sẽ không nhớ bạn đã quát gì, nhưng sẽ mãi mãi khắc ghi ánh mắt, gương mặt bạn khi quát mắng.

Thế hệ cợt nhả tiêu tiền “ngược đời” không giống ai

Phong cách sống - Ngọc Linh - CFB - 24/07/2025 10:00
Tiêu dùng ngược trong mắt người khác cũng chẳng sao, chỉ cần bản thân thấy “xuôi” là được rồi vì tiền là của mình cơ mà.

Trở về từ cõi chết

Tủ sách - FN - 24/07/2025 09:00
Trở về từ cõi chết là quyển tự truyện sâu sắc của tác giả Anita Moorjani, kể về hành trình phi thường của cô từ cõi chết trở về và những bài học quý giá mà cô đã học được từ trải nghiệm cận tử.

Đại địa chấn kinh tế Kỳ 4: Bài học từ cuộc đại khủng hoảng Covid-19

Từ sách - Phim - Quang Thanh - 24/07/2025 08:00
Bất chấp tình hình kinh tế cuối năm u ám, thị trường chứng khoán vẫn đạt được các đỉnh mới nhờ căng thẳng địa-chính trị được cải thiện và quan trọng nhất là nhờ những loại vắc-xin Covid-19 đầu tiên được chấp thuận.

Thái độ xấu

Blog GS John VU - GS John Vu - 23/07/2025 13:00
Ớ Ấn Độ, nhiều người lập trình đi làm với thái độ xấu bởi vì họ biết rằng họ có thể dễ dàng kiếm được việc làm với các công ti khác vì tình trạng thiếu hụt công nhân phần mềm.

Hỏi DeepSeek 6 điều ‘đau đầu’ nhất về cách dạy con: Câu trả lời khiến tôi bừng tỉnh

Kỹ năng - Diệu Đan - CFB - 23/07/2025 11:00
Trước những băn khoăn, tôi tìm đến DeepSeek, và câu trả lời của DeepSeek khiến tôi bừng tỉnh. Hoá ra bấy lâu nay, tôi đã dạy con sai cách!
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ứ 7, 26/07/2025