Làm thế nào một Bài Đăng Ẩn Danh trên 4chan Giúp Giải Quyết Một Bài Toán Toán Học 25 Năm

Vào ngày 16 tháng 9, 2011, một fan anime đăng một câu hỏi toán học lên diễn đàn trực tuyến 4chan về series truyền hình cult classic The Melancholy of Haruhi Suzumiya. Mùa đầu của series, liên quan đến việc du hành thời gian, đã phát sóng ban đầu không theo trình tự thời gian, và phiên tái phát sóng cũng như phiên bản DVD đã sắp xếp lại các tập phim. Các fan tranh luận trực tuyến về thứ tự tốt nhất để xem các tập phim, và người đăng bài trên 4chan tự hỏi: Nếu người xem muốn xem series theo mọi thứ tự có thể, danh sách ngắn nhất các tập họ phải xem là gì?

Chưa đầy một giờ sau đó, một người ẩn danh đưa ra một câu trả lời - không phải là một giải pháp hoàn chỉnh, mà là một giới hạn dưới về số tập phim cần thiết. Bằng chứng này, bao gồm cả series có bất kỳ số tập phim nào, cho thấy rằng đối với mùa đầu tiên gồm 14 tập của Haruhi, người xem ít nhất phải xem 93.884.313.611 tập để xem tất cả các thứ tự có thể. “Vui lòng xem xét [bằng chứng] của tôi để xem có những lỗ hổng nào tôi có thể đã bỏ qua không,” người đăng bài ẩn danh viết.

Bằng chứng này đã không được cộng đồng toán học chú ý trong bảy năm - dường như chỉ có một nhà toán học chuyên nghiệp phát hiện ra nó vào thời điểm đó, và ông ấy không kiểm tra nó một cách cẩn thận. Nhưng trong một bất ngờ vào tháng trước, nhà văn khoa học viễn tưởng người Australia Greg Egan đã chứng minh một giới hạn trên mới về số tập phim cần thiết. Phát hiện của Egan đánh thức lại sự quan tâm vào vấn đề và gây chú ý đến giới hạn dưới được đăng ẩn danh vào năm 2011. Cả hai bằng chứng đều được ca ngợi là những tiến bộ đáng kể trong một câu đố mà các nhà toán học đã nghiên cứu ít nhất là 25 năm.

Các nhà toán học nhanh chóng xác minh giới hạn trên của Egan, giống như giới hạn dưới, áp dụng cho series có bất kỳ độ dài nào. Sau đó, Robin Houston, một nhà toán học tại công ty trực quan hóa dữ liệu Kiln, và Jay Pantone của Đại học Marquette tại Milwaukee độc lập xác minh công việc của người đăng bài ẩn danh trên 4chan. “Việc cố gắng xác định xem đó có đúng không mất rất nhiều công sức,” Pantone nói, vì ý tưởng chính chưa được diễn đạt một cách đặc biệt rõ ràng.

Hiện nay, Houston và Pantone, cùng với Vince Vatter của Đại học Florida tại Gainesville, đã viết lên bản luận điểm chính thức. Trong bài báo của họ, họ liệt kê tác giả đầu tiên là “Người Đăng Bài Ẩn Danh trên 4chan.”

Nếu một series TV chỉ có ba tập, có sáu thứ tự khả dĩ để xem chúng: 123, 132, 213, 231, 312 và 321. Bạn có thể xếp sáu chuỗi này lại để tạo thành một danh sách gồm 18 tập phim bao gồm mọi thứ tự, nhưng có một cách hiệu quả hơn nhiều: 123121321. Một chuỗi như thế này chứa mọi sắp xếp có thể (hoặc hoán vị) của một bộ sưu tập gồm n ký tự được gọi là “siêu hoán vị.

Vào năm 1993, Daniel Ashlock và Jenett Tillotson quan sát rằng nếu bạn nhìn vào siêu hoán vị ngắn nhất cho các giá trị khác nhau của n, một mô hình nhanh chóng xuất hiện liên quan đến giai thừa - những số đó, được viết dưới dạng n!, bao gồm việc nhân tất cả các số lên đến n với nhau (ví dụ, 4! = 4 × 3 × 2 × 1).

Nếu series của bạn chỉ có một tập, siêu hoán vị ngắn nhất có độ dài là 1! (cũng gọi là chỉ là 1). Đối với một series hai tập, siêu hoán vị ngắn nhất (121) có độ dài là 2! + 1!. Đối với ba tập (ví dụ mà chúng ta đã xem ở trên), độ dài là 3! + 2! + 1!, và đối với bốn tập (123412314231243121342132413214321), nó là 4! + 3! + 2! + 1!. Quy tắc giai thừa cho siêu hoán vị trở thành trí tuệ thông thường (mặc dù không ai có thể chứng minh nó đúng cho mọi giá trị của n), và các nhà toán học sau đó xác nhận nó cho n = 5.

Sau đó, vào năm 2014, Houston làm cho các nhà toán học kinh ngạc khi chỉ ra rằng đối với n = 6, mô hình bị phá vỡ. Quy tắc giai thừa dự đoán rằng để xem sáu tập theo mọi thứ tự sẽ yêu cầu 873 tập, nhưng Houston đã tìm ra cách để làm điều đó trong 872 tập. Và vì có một cách đơn giản để chuyển đổi một siêu hoán vị ngắn trên n ký tự thành một siêu hoán vị ngắn trên n + 1 ký tự, ví dụ của Houston có nghĩa là quy tắc giai thừa không đúng cho mọi giá trị của n lớn hơn 6.

Công trình của Houston hoạt động bằng cách chuyển đổi vấn đề siêu hoán vị thành vấn đề người bán hàng lữ hành nổi tiếng, tìm kiếm đường đi ngắn nhất qua một bộ sưu tập các thành phố. Cụ thể hơn, siêu hoán vị liên quan đến vấn đề người bán hàng lữ hành “bất đối xứng”, trong đó mỗi đường đi giữa hai thành phố có một chi phí (không nhất thiết phải giống nhau ở cả hai hướng), và mục tiêu là tìm đường đi ít tốn kém nhất qua tất cả các thành phố.

Sự chuyển đổi này đơn giản: Hãy coi mỗi hoán vị như một “thành phố” và tưởng tượng một đường đi từ mỗi hoán vị đến mỗi hoán vị khác. Trong vấn đề siêu hoán vị, chúng ta muốn một chuỗi chữ số ngắn nhất có thể liệt kê tất cả các hoán vị, vì vậy mục tiêu là đi qua các hoán vị một cách ít chữ số nhất từ hoán vị ban đầu. Vì vậy, chúng ta xác định chi phí cho mỗi đường đi là chỉ số chữ số chúng ta phải gắn vào cuối hoán vị đầu tiên để có được hoán vị thứ hai. Trong ví dụ n = 3, ví dụ, đường đi từ 231 đến 312 có chi phí $1, vì chúng ta chỉ cần thêm số 2 vào cuối của 231 để có được 312, trong khi đường đi từ 231 đến 132 có chi phí $2, vì chúng ta phải thêm số 32. Với thiết lập này, đường đi ít tốn kém nhất qua các thành phố tương ứng trực tiếp với siêu hoán vị ngắn nhất.

Sự chuyển đổi này có nghĩa là Houston có thể áp dụng sức mạnh của các thuật toán người bán hàng lữ hành vào vấn đề siêu hoán vị. Vấn đề người bán hàng lữ hành nổi tiếng là một vấn đề NP-khó, có nghĩa là không có thuật toán hiệu quả nào có thể giải quyết tất cả các trường hợp của nó. Nhưng có các thuật toán có thể giải quyết một số trường hợp một cách hiệu quả và các thuật toán khác tạo ra các giải pháp gần đúng tốt. Houston sử dụng một trong những thuật toán sau để tạo ra siêu hoán vị của mình có 872 chữ số.

Vì anh chỉ tạo ra một giải pháp gần đúng, có thể không phải là siêu hoán vị tốt nhất. Các nhà toán học hiện đang tiến hành một cuộc tìm kiếm toàn cầu trên máy tính để tìm siêu hoán vị ngắn nhất trên sáu ký tự, Pantone nói. “Chúng tôi biết cuộc tìm kiếm của chúng tôi sẽ kết thúc trong thời gian hữu hạn, nhưng không biết đó là một tuần hay một triệu năm,” ông nói. “Không có thanh tiến độ nào.”

Đến thời điểm của công trình của Houston, bài đăng ẩn danh trên 4chan đã nằm yên trong góc của internet gần ba năm. Một nhà toán học, Nathaniel Johnston của Đại học Mount Allison, đã nhận ra một bản sao của bài đăng trên một trang web khác vài ngày sau khi nó được đăng - không phải vì ông là fan anime, mà vì ông đã gõ một loạt các từ khóa liên quan đến siêu hoán vị vào Google.

Johnston đọc lập luận và nghĩ rằng nó có vẻ hợp lý, nhưng ông không bỏ nhiều công sức vào việc kiểm tra nó một cách cẩn thận. Vào thời điểm đó, các nhà toán học tin rằng công thức giai thừa cho siêu hoán vị có lẽ là đúng, và khi bạn nghĩ bạn biết đáp án chính xác của một câu hỏi, một giới hạn dưới không thực sự thú vị. Nói cách khác, các tập phim nghiên cứu về siêu hoán vị đang được phát sóng theo thứ tự không đúng.

Johnston sau đó đề cập đến giới hạn dưới trên một vài trang web, nhưng “Tôi không nghĩ có ai thực sự để ý đến nó một cách đặc biệt,” Houston nói.

Sau đó, vào ngày 26 tháng 9 năm nay, nhà toán học John Baez của Đại học California, Riverside, đăng trên Twitter về phát hiện năm 2014 của Houston, như một phần của loạt tweet về các mô hình toán học rõ ràng nhưng thất bại. Tweet của ông thu hút sự chú ý của Egan, người đã từng là chuyên ngành toán học hàng thập kỷ trước khi ông bắt đầu sự nghiệp viết văn khoa học nổi tiếng (cuốn tiểu thuyết nổi tiếng của ông vào năm 1994, một sự trùng hợp hạnh phúc, được gọi là Thành Phố Hoán Vị). “Tôi chưa bao giờ ngừng quan tâm đến [toán học],” Egan viết trong email.

Egan tự hỏi liệu có thể xây dựng siêu hoán vị ngắn hơn cả của Houston hay không. Ông lục lọi văn bản chuyên ngành để tìm hiểu về cách xây dựng đường đi ngắn qua mạng lưới hoán vị, và sau vài tuần tìm thấy đúng những gì ông cần. Trong một hoặc hai ngày, ông đã đưa ra một giới hạn trên mới về độ dài của siêu hoán vị ngắn nhất cho n ký tự: n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3. Nó tương tự như công thức giai thừa cũ, nhưng loại bỏ nhiều thuật ngữ.

“Nó hoàn toàn hủy diệt [giới hạn trên trước đó],” Houston nói.

Giới hạn dưới của bài đăng ẩn danh trên 4chan, trong khi đó, gần với giới hạn trên mới: Nó dẫn đến n! + (n – 1)! + (n – 2)! + n – 3. Khi kết quả của Egan trở nên công khai, Johnston nhắc nhở những nhà toán học khác về chứng minh của bài đăng ẩn danh, và sau đó Houston và Pantone nhanh chóng chứng minh rằng nó đúng. Giống như công việc của Houston, cả giới hạn dưới và giới hạn trên mới đều đến từ vấn đề người bán hàng lữ hành: Giới hạn dưới chỉ ra rằng một tuyến đường qua tất cả các thành phố phải đi qua một số tối thiểu các đường đi có chi phí lớn hơn 1 đô la, trong khi giới hạn trên xây dựng một tuyến đường cụ thể cho mỗi n sử dụng chỉ các kết nối 1 và 2 đô la.

Đối với người hâm mộ Haruhi, công trình của Egan cung cấp hướng dẫn cụ thể về cách xem tất cả các thứ tự có thể của mùa 1 chỉ trong 93,924,230,411 tập. Người xem có thể bắt đầu xem liền hoặc họ có thể chờ xem liệu các nhà toán học có thể làm giảm con số này xuống không. Giới hạn dưới của bài đăng ẩn danh chứng minh rằng việc làm giảm không thể tiết kiệm hơn khoảng 40 triệu tập - nhưng đó là đủ để bắt đầu một cách tốt cho mùa 2.

Câu chuyện gốc được tái in với sự cho phép từ Quanta Magazine, một tờ báo độc lập về nội dung thuộc Quỹ Simons với nhiệm vụ tăng cường sự hiểu biết của công chúng về khoa học thông qua việc báo cáo về các phát triển và xu hướng nghiên cứu trong toán học và các ngành khoa học tự nhiên và sinh học.

• Chìa khóa cho một cuộc sống lâu dài ít liên quan đến “di truyền tốt”
• Bitcoin sẽ làm đốt cháy hành tinh. Câu hỏi: nhanh chóng như thế nào?
• Apple sẽ tiếp tục làm chậm iPhone. Đây là cách để ngăn chặn nó
• Sự mê hoặc với tội ác thực sự ngày nay liệu có thực sự về tội ác thực sự không?
• Một vận động viên marathon lớn tuổi cố gắng chạy nhanh sau tuổi 40
• Tìm kiếm thêm? Đăng ký bản tin hàng ngày của chúng tôi và không bao giờ bỏ lỡ những câu chuyện mới nhất và tuyệt vời nhất của chúng tôi