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

Những linh vật rồng hài hước khiến người xem bật cười ở Trung Quốc

2024 là năm Giáp Thìn. Không chỉ ở Việt Nam, hình tượng linh vật rồng cũng được chú ý tại một số quốc gia trên thế giới, đặc biệt là những nước có cộng đồng người Hoa sinh sống.
2

Trận đấu voi lịch sử giữa voi châu Á và voi châu Phi: Kết quả khó tin

Trong trận chiến Raphia ở Palestine, vào năm 217 trước Công nguyên, đã xảy ra cuộc đụng độ đẫm máu giữa tượng binh dùng voi châu Á và voi châu Phi.
3

Vì sao tượng binh nhanh chóng vào viện bảo tàng?

Trong khi kỵ binh phải sau Thế chiến thứ nhất mới dừng sứ mệnh thì tượng binh vào viện bảo tàng sớm hơn.
5

6 sự thật về thế giới khó tin đến nỗi chưa ai từng nghĩ đến

Thiên nhiên, con người và động vật trên thế giới luôn ẩn chứa những sự thật làm chúng ta không khỏi ngạc nhiên.

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.

Phát kiến công nghệ di động

Blog GS John VU - GS John Vu - 02/03/2024 12:00
Công nghệ di động đang ngày càng trở thành cần thiết trên khắp thế giới.

Truyện Kim Dung - Vô Danh Thần Tăng đấu với Độc Cô Cầu Bại, ai thắng?

Thư giãn - Nguyệt Phạm - 02/03/2024 11:00
Vô Danh Thần Tăng và Độc Cô Cầu Bại đều là cao thủ trong giới võ lâm, khi đối đầu thì ai sẽ là người giành lợi thế?

Lạc lối là bình thường, nhưng đừng lạc quá lâu: 7 điều giúp bạn đi đúng hướng, sống hài lòng và hạnh phúc

Suy ngẫm - Trung Hạ - 02/03/2024 10:00
Cách để thoát khỏi trạng thái mơ hồ ấy lắm lúc lại đơn giản vô cùng. Đôi khi chỉ cần tạo một thói quen nhỏ, cũng có thể thay đổi cả đời người.

Chữa lành đứa trẻ tổn thương bên trong - Điều kỳ diệu mà bạn có thể tự mang lại cho mình

Từ sách - Phim - FN - 02/03/2024 09:00
Trong tâm hồn bạn có một đứa trẻ bị tổn thương, lạc lối. Nỗi đau đó liên tục bộc lộ ra trong cuộc đời bạn, dưới dạng những phản ứng bốc đồng và nhũng kiểu phản hồi cảm xúc thái quá.

Tài chính cho mọi người - Vì sao chúng ta luôn có thái độ kỳ lạ với tiền bạc?

Từ sách - Phim - YÊN VŨ - 02/03/2024 08:00
Có một thực tế là, phần lớn chúng ta đều có thái độ kỳ lạ với tiền bạc. Chúng ta né tránh việc trò chuyện về tiền bạc, thậm chí, một số người còn cho rằng đây là nói đến tiền bạc là chuyện đáng xấu hổ.

Tạo ra tổ và làm việc tổ

Blog GS John VU - GS John Vu - 01/03/2024 13:00
Công việc công nghệ thông tin (CNTT) yêu cầu các công nhân làm việc trong tổ. Làm việc tổ là một trong những kĩ năng mềm quan trọng mà sinh viên phải có và thường được hỏi tới trong phỏng vấn việc làm.

Nguồn gốc của trò chơi lô tô

Giải trí - Tiểu Vũ - 01/03/2024 12:00
Lô tô là trò chơi rất phổ biến ở miền Nam, cách diễn xướng âm nhạc gần gũi này đã trở thành nét văn hóa đặc sắc của người dân vùng đất này.

6 sự thật về thế giới khó tin đến nỗi chưa ai từng nghĩ đến

Thư giãn - Thanh Tâm - 01/03/2024 11:00
Thiên nhiên, con người và động vật trên thế giới luôn ẩn chứa những sự thật làm chúng ta không khỏi ngạc nhiên.

Bài phát biểu gây sốt: Muốn về sau không sống lay lắt qua ngày, nhất định phải lưu ý 3 điều này

Suy ngẫm - Hữu Đan - 01/03/2024 10:00
Nếu bạn là sinh viên, hãy nhớ đọc kỹ; nếu bạn là phụ huynh, hãy nhớ truyền lại cho con mình vì nó rất hữu ích.

"Siêu phẩm" dài 9 phút được quay trong 24 năm tiết lộ: "Bí mật" đằng sau một đứa trẻ thiên tài

Truyền cảm hứng - Hiểu Đan - 01/03/2024 09:00
Sự giáo dục, sự quan sát cẩn thận và tôn trọng từ khi còn nhỏ đã tạo điều kiện cho sự ra đời và trưởng thành của một “cô gái thiên tài”.

Cởi trói linh hồn - Cách mà tâm trí bạn vận hành để điều khiển những trải nghiệm

Từ sách - Phim - Quìn - 01/03/2024 08:00
Những gì bạn đang cảm nhận về thế giới thực ra là một sự diễn đạt hoàn toàn mang tính cá nhân của riêng bạn chứ không phải là kinh nghiệm nguyên sơ.

Học từ thất bại

Blog GS John VU - GS John Vu - 29/02/2024 13:00
Hệ thống giáo dục châu Á có nhiều kì thi để chọn chỉ vài học sinh xuất chúng. Do đó khi học sinh thất bại, họ bị loại ra khỏi hệ thống giáo dục cho nên mục đích của học sinh là qua được kì thi.

Bạn muốn hẹn hò - Mẹ đơn thân bán cháo vịt hẹn hò với người đàn ông U50 làm chăn nuôi

Truyền hình - Lam Phương - 29/02/2024 12:00
Hoàng Liên Hải (SN 1982) và Nguyễn Thị Ngân (SN 1982) đều từng trải qua hôn nhân đổ vỡ, mong muốn tìm người bầu bạn khi về già.

Sora khiến Trung Quốc như bị tụt hậu về AI tạo sinh - phần 2

Thư giãn - Sơn Vân - 29/02/2024 11:00
Với khả năng tạo video chân thực từ văn bản, Sora đã mang đến nhiều đồn đoán về bí mật đằng sau hiệu suất ấn tượng của nó.

Chuyên gia Harvard: Ở chốn công sở không bao giờ để lộ điều này

Kỹ năng - Phương Mộc - 29/02/2024 10:00
Bạn phải hiểu rằng, làm mất lòng người khác cũng sẽ khiến con đường phát triển cá nhân thêm khó khă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ứ 7, 02/03/2024