đéo có hình chó nó tin
Cái nồi có lắp
Các giải pháp toán học có thể được tìm thấy ở những nơi đáng ngạc nhiên, bao gồm cả thế giới ngầm của Internet. Vào năm 2011, một người dùng ẩn danh trên diễn đàn hình ảnh 4chan đã đặt ra một câu đố toán học về bộ anime kinh điển The Melancholy of Haruhi Suzumiya. Mặc dù diễn đàn này tràn ngập những nội dung thù hận, bạo lực và cực đoan, bài đăng ban đầu đó đã dẫn đến một giải pháp cho bài toán toán học phức tạp.
Mùa đầu tiên của bộ anime này bao gồm 14 tập được thiết kế để bạn có thể xem chúng theo bất kỳ thứ tự nào bạn muốn. (Dành cho những người không quen thuộc với thế giới anime: một bộ phim kinh dị hành động gồm tám phần có tên Kaleidoscope trên Netflix cũng tuân theo nguyên tắc tương tự). Tại một thời điểm nào đó trong cuộc thảo luận năm 2011 về bộ truyện trên 4chan, ai đó đã hỏi số lượng tập tối thiểu mà họ sẽ phải xem để đã xem nó theo mọi thứ tự có thể.
Trên thực tế, câu hỏi này có liên quan đến cái gọi là siêu hoán vị (superpermutations). Và hóa ra, lĩnh vực toán học này chứa đựng nhiều câu đố: cho đến ngày nay, các nhà toán học vẫn không thể trả lời đầy đủ bài toán mà người dùng 4chan đã đặt ra.
Nhưng thật đáng kinh ngạc, trong cuộc thảo luận đó, một trong những người dùng ẩn danh đã đưa ra ước tính về số lượng tối thiểu của tất cả các tập cần xem với một cách tiếp cận mà trước đây các nhà toán học chưa biết đến. "Tôi sẽ cần [nói rõ] điều này trong nhiều bài đăng. Vui lòng xem xét nó xem có bất kỳ lỗ hổng nào mà tôi có thể đã bỏ qua không," người dùng viết, giải thích trong một vài bước cách họ đi đến ước tính của mình. Những người dùng khác sau đó đã tiếp nhận các lập luận và thảo luận về chúng - nhưng bên ngoài 4chan, không ai trong số này tạo ra bất kỳ làn sóng nào. Dường như không ai để ý. Trong toán học, hai đối tượng hoán vị khi chúng được sắp xếp lại hoặc kết hợp lại. Ví dụ, bạn có thể hoán vị AB thành BA. Nếu một bộ anime chỉ bao gồm hai phần, bạn có thể xem phần đầu tiên và sau đó là phần thứ hai (1-2) hoặc phần thứ hai và sau đó là phần đầu tiên (2-1).
Nếu bạn muốn xem một bộ phim theo nhiều cách sắp xếp - có lẽ để tìm ra trình tự các tập phim nào có ý nghĩa nhất - bạn cần một siêu hoán vị. Đây là một chuỗi của tất cả các hoán vị có thể. Hãy tưởng tượng một buổi chiếu marathon nơi bạn xem tập đầu tiên, sau đó là tập thứ hai, và sau đó xem tập thứ hai, sau đó là tập đầu tiên (1-2-2-1). Để tránh xem tập thứ hai hai lần liên tiếp, một siêu hoán vị ngắn hơn sẽ là 1-2-1; bạn sẽ chỉ phải xem ba tập để vẫn bao gồm mọi thứ tự có thể.
Nếu một bộ phim bao gồm ba tập, việc tìm siêu hoán vị ngắn nhất sẽ khó hơn một chút. Trong trường hợp này, có 3! = 6 trình tự khác nhau: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. May mắn thay, bạn không cần phải xem 3 × 6 = 18 phần mà có thể tìm thấy một lối tắt thông minh, trong trường hợp này: 1-2-3-1-2-1-3-2-1. Thứ tự đó chứa tất cả các hoán vị có thể có của các số 1, 2 và 3, nhưng bạn chỉ phải xem chín tập! Các nhà toán học cũng đã tính toán các siêu hoán vị ngắn nhất cho một bộ phim bao gồm n = 4 và n = 5 tập (tương ứng là 33 và 153 tập). Tuy nhiên, ngoài điều đó, họ đang ở trong bóng tối. Các siêu hoán vị ngắn nhất cho n > 5 không được biết.
Trên thực tế, thách thức liên quan đến một trong những bài toán khó giải quyết nhất trong thuật toán: bài toán người bán hàng du lịch. Trong bài toán này, một người muốn đến thăm các thành phố khác nhau và cuối cùng trở về quê hương của họ. Nhiệm vụ là tìm ra con đường ngắn nhất kết nối tất cả các thành phố. Siêu hoán vị ngắn nhất là một biến thể của bài toán này, trong đó các hoán vị riêng lẻ đại diện cho các thành phố khác nhau. Trong trường hợp này, bạn gán các khoảng cách khác nhau giữa các thành phố bằng cách xác định sự chồng chéo của các hoán vị. Ví dụ: các thành phố 1-2-3 và 2-3-1 có sự chồng chéo lớn: hai chữ số cuối cùng của hoán vị đầu tiên khớp với hai chữ số đầu tiên của hoán vị thứ hai, vì vậy chúng có thể được kết hợp để tạo thành 1-2-3-1. Do đó, chúng ta có thể gán một khoảng cách ngắn giữa hai thành phố đó. Mặt khác, 1-2-3 và 2-1-3 không trùng nhau. (Để xem cả hai chuỗi, bạn phải xem đầy đủ sáu phần; không có lối tắt nào có thể.) Do đó, các thành phố này có một khoảng cách lớn giữa chúng.
Để tìm tuyến đường ngắn nhất trong các hoán vị, bạn kết nối các hoán vị chồng chéo nhiều nhất. Chỉ có một khó khăn: không có thuật toán nào được biết đến có thể giải quyết bài toán người bán hàng du lịch một cách nhanh chóng. Nếu chúng ta đang xử lý một vài thành phố - hoặc, trong trường hợp của một bộ anime, một vài tập - đây không phải là một nhược điểm lớn. Nhưng ngay khi n trở nên lớn, các máy tính sẽ thất bại trong nhiệm vụ vì thời gian tính toán tăng theo cấp số nhân với n.
Máy tính có thể tính toán siêu hoán vị cho n = 4 và n = 5 nhưng không thể tính toán bất kỳ thứ gì vượt quá điều đó. Và mặc dù có thể tính toán các siêu hoán vị phức tạp cho các số lớn hơn, nhưng việc tìm siêu hoán vị ngắn nhất trở nên khó khăn hơn.
Do đó, các chuyên gia phải thực hiện các ước tính. Ví dụ, có một thuật toán giúp ước tính độ dài của siêu hoán vị ngắn nhất có thể cho n đối tượng: 1! + 2! + 3! + ... + n! Sử dụng thuật toán đó, nếu n = 2, bạn nhận được một siêu hoán vị có độ dài 1 + 2 = 3. Đối với n = 3, điều này dẫn đến độ dài 1 + 2 + 6 = 9. Đối với n = 4, bạn nhận được 33. Và đối với n = 5, bạn nhận được 153, tương ứng với siêu hoán vị ngắn nhất trong mỗi trường hợp.
Tuy nhiên, đối với n lớn hơn, thuật toán này không còn áp dụng: máy tính đã có thể tìm thấy các siêu hoán vị ngắn hơn so với những gì nó gợi ý. Trên thực tế, công thức 1! + 2! + 3! + ... + n! ước tính quá cao độ dài của siêu hoán vị ngắn nhất đối với n lớn. Mặc dù thuật toán chỉ đưa ra một câu trả lời gần đúng, các nhà toán học sử dụng nó làm điểm khởi đầu, với mục tiêu thu hẹp các lựa chọn để tìm ra câu trả lời chính xác hơn.
Năm 2013, Nathaniel Johnston, hiện là giáo sư toán học tại Đại học Mount Allison ở New Brunswick, đã tìm thấy một trang fandom của Melancholy of Haruhi Suzumiya. Bản thân Johnston không phải là một fan hâm mộ anime. Anh đã đến trang web sau khi tìm kiếm một số thuật ngữ liên quan đến siêu hoán vị. Ở đó, anh đã bắt gặp cuộc thảo luận đã được tổ chức trên 4chan gần hai năm trước đó, mà một người dùng đã sao chép vào trang fandom.
Johnston đã không bận tâm đến việc tính toán mà đã trích dẫn bài đăng trên fandom trên blog của mình. Bình luận này cũng không được chú ý trong vài năm. Sau đó, vào tháng 10 năm 2018, nhà toán học Robin Houston đã tình cờ thấy bài đăng trên blog của đồng nghiệp của mình thông qua một sự trùng hợp kỳ lạ. Houston vừa mới biết rằng tác giả khoa học viễn tưởng người Úc Greg Egan đã tìm thấy độ dài tối đa mới cho các siêu hoán vị ngắn nhất, được biểu thị là:
n! +(n –1)! + (n – 2)! + (n – 3)! + n – 3
Điều đó tự nó đã kỳ lạ. Nhưng khi Houston bắt đầu tìm hiểu thêm về kết quả này, anh nhận ra rằng độ dài tối thiểu của một siêu hoán vị đã được một người dùng ẩn danh của fandom anime đưa ra một giá trị mới (anh không biết về nguồn gốc trên 4chan vào thời điểm đó). Công thức cho độ dài tối thiểu là:
n! +(n – 1)! + (n – 2)! + n – 3
Houston đã chia sẻ khám phá của mình trên Twitter (nay là X) vào ngày 23 tháng 10 năm đó. "Một tình huống kỳ lạ. Giới hạn dưới tốt nhất được biết đến cho độ dài tối thiểu của siêu hoán vị đã được chứng minh bởi một người dùng ẩn danh của một wiki chủ yếu dành cho anime," anh viết.
Cùng với các đồng nghiệp của mình, các nhà toán học Jay Pantone và Vince Vatter, Houston đã quyết định kiểm tra bằng chứng của người dùng 4chan và viết nó ra một cách toán học. Các nhà nghiên cứu đã đăng công trình toán học của họ lên Bách khoa toàn thư trực tuyến về dãy số nguyên trong cùng tháng đó, và tác giả đầu tiên được liệt kê là "Người đăng ẩn danh 4chan."
Vậy những công thức này cho chúng ta biết điều gì? Nếu bạn muốn xem tất cả các tập của một bộ phim gồm n phần theo tất cả các kết hợp có thể, bạn phải xem ít nhất n! +(n – 1)! + (n – 2)! + n – 3 tập—đó là đóng góp của người dùng 4chan—và nhiều nhất là n! +(n – 1)! + (n – 2)! + (n – 3)! + n – 3, điều mà chúng ta biết thông qua công trình của Egan.
Trong trường hợp của series tám tập Kaleidoscope, bạn sẽ phải xem ít nhất 46.085 tập và nhiều nhất là 46.205 tập. Đối với The Melancholy of Haruhi Suzumiya có 14 tập, con số tăng lên đáng kể: tối thiểu 93.884.313.611 tập và tối đa 93.924.230.411. Hãy nhớ rằng đây không phải là một giải pháp hoàn chỉnh—nó chỉ đặt ra một phạm vi cho kích thước của một siêu hoán vị cho phép bạn xem phim một cách hiệu quả theo mọi thứ tự có thể.
May mắn thay, Egan cũng cung cấp một thuật toán để xây dựng siêu hoán vị tương ứng. Điều này cho phép người hâm mộ Haruhi tìm ra thứ tự xem các tập tốt nhất. Nhưng với thời lượng trung bình của một tập là khoảng 24 phút, sẽ mất khoảng 4 triệu năm để xem hết siêu hoán vị này.
vnreview.vn
Mùa đầu tiên của bộ anime này bao gồm 14 tập được thiết kế để bạn có thể xem chúng theo bất kỳ thứ tự nào bạn muốn. (Dành cho những người không quen thuộc với thế giới anime: một bộ phim kinh dị hành động gồm tám phần có tên Kaleidoscope trên Netflix cũng tuân theo nguyên tắc tương tự). Tại một thời điểm nào đó trong cuộc thảo luận năm 2011 về bộ truyện trên 4chan, ai đó đã hỏi số lượng tập tối thiểu mà họ sẽ phải xem để đã xem nó theo mọi thứ tự có thể.
Trên thực tế, câu hỏi này có liên quan đến cái gọi là siêu hoán vị (superpermutations). Và hóa ra, lĩnh vực toán học này chứa đựng nhiều câu đố: cho đến ngày nay, các nhà toán học vẫn không thể trả lời đầy đủ bài toán mà người dùng 4chan đã đặt ra.
Nhưng thật đáng kinh ngạc, trong cuộc thảo luận đó, một trong những người dùng ẩn danh đã đưa ra ước tính về số lượng tối thiểu của tất cả các tập cần xem với một cách tiếp cận mà trước đây các nhà toán học chưa biết đến. "Tôi sẽ cần [nói rõ] điều này trong nhiều bài đăng. Vui lòng xem xét nó xem có bất kỳ lỗ hổng nào mà tôi có thể đã bỏ qua không," người dùng viết, giải thích trong một vài bước cách họ đi đến ước tính của mình. Những người dùng khác sau đó đã tiếp nhận các lập luận và thảo luận về chúng - nhưng bên ngoài 4chan, không ai trong số này tạo ra bất kỳ làn sóng nào. Dường như không ai để ý. Trong toán học, hai đối tượng hoán vị khi chúng được sắp xếp lại hoặc kết hợp lại. Ví dụ, bạn có thể hoán vị AB thành BA. Nếu một bộ anime chỉ bao gồm hai phần, bạn có thể xem phần đầu tiên và sau đó là phần thứ hai (1-2) hoặc phần thứ hai và sau đó là phần đầu tiên (2-1).
Nếu bạn muốn xem một bộ phim theo nhiều cách sắp xếp - có lẽ để tìm ra trình tự các tập phim nào có ý nghĩa nhất - bạn cần một siêu hoán vị. Đây là một chuỗi của tất cả các hoán vị có thể. Hãy tưởng tượng một buổi chiếu marathon nơi bạn xem tập đầu tiên, sau đó là tập thứ hai, và sau đó xem tập thứ hai, sau đó là tập đầu tiên (1-2-2-1). Để tránh xem tập thứ hai hai lần liên tiếp, một siêu hoán vị ngắn hơn sẽ là 1-2-1; bạn sẽ chỉ phải xem ba tập để vẫn bao gồm mọi thứ tự có thể.
Nếu một bộ phim bao gồm ba tập, việc tìm siêu hoán vị ngắn nhất sẽ khó hơn một chút. Trong trường hợp này, có 3! = 6 trình tự khác nhau: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. May mắn thay, bạn không cần phải xem 3 × 6 = 18 phần mà có thể tìm thấy một lối tắt thông minh, trong trường hợp này: 1-2-3-1-2-1-3-2-1. Thứ tự đó chứa tất cả các hoán vị có thể có của các số 1, 2 và 3, nhưng bạn chỉ phải xem chín tập! Các nhà toán học cũng đã tính toán các siêu hoán vị ngắn nhất cho một bộ phim bao gồm n = 4 và n = 5 tập (tương ứng là 33 và 153 tập). Tuy nhiên, ngoài điều đó, họ đang ở trong bóng tối. Các siêu hoán vị ngắn nhất cho n > 5 không được biết.
Trên thực tế, thách thức liên quan đến một trong những bài toán khó giải quyết nhất trong thuật toán: bài toán người bán hàng du lịch. Trong bài toán này, một người muốn đến thăm các thành phố khác nhau và cuối cùng trở về quê hương của họ. Nhiệm vụ là tìm ra con đường ngắn nhất kết nối tất cả các thành phố. Siêu hoán vị ngắn nhất là một biến thể của bài toán này, trong đó các hoán vị riêng lẻ đại diện cho các thành phố khác nhau. Trong trường hợp này, bạn gán các khoảng cách khác nhau giữa các thành phố bằng cách xác định sự chồng chéo của các hoán vị. Ví dụ: các thành phố 1-2-3 và 2-3-1 có sự chồng chéo lớn: hai chữ số cuối cùng của hoán vị đầu tiên khớp với hai chữ số đầu tiên của hoán vị thứ hai, vì vậy chúng có thể được kết hợp để tạo thành 1-2-3-1. Do đó, chúng ta có thể gán một khoảng cách ngắn giữa hai thành phố đó. Mặt khác, 1-2-3 và 2-1-3 không trùng nhau. (Để xem cả hai chuỗi, bạn phải xem đầy đủ sáu phần; không có lối tắt nào có thể.) Do đó, các thành phố này có một khoảng cách lớn giữa chúng.
Để tìm tuyến đường ngắn nhất trong các hoán vị, bạn kết nối các hoán vị chồng chéo nhiều nhất. Chỉ có một khó khăn: không có thuật toán nào được biết đến có thể giải quyết bài toán người bán hàng du lịch một cách nhanh chóng. Nếu chúng ta đang xử lý một vài thành phố - hoặc, trong trường hợp của một bộ anime, một vài tập - đây không phải là một nhược điểm lớn. Nhưng ngay khi n trở nên lớn, các máy tính sẽ thất bại trong nhiệm vụ vì thời gian tính toán tăng theo cấp số nhân với n.
Máy tính có thể tính toán siêu hoán vị cho n = 4 và n = 5 nhưng không thể tính toán bất kỳ thứ gì vượt quá điều đó. Và mặc dù có thể tính toán các siêu hoán vị phức tạp cho các số lớn hơn, nhưng việc tìm siêu hoán vị ngắn nhất trở nên khó khăn hơn.
Do đó, các chuyên gia phải thực hiện các ước tính. Ví dụ, có một thuật toán giúp ước tính độ dài của siêu hoán vị ngắn nhất có thể cho n đối tượng: 1! + 2! + 3! + ... + n! Sử dụng thuật toán đó, nếu n = 2, bạn nhận được một siêu hoán vị có độ dài 1 + 2 = 3. Đối với n = 3, điều này dẫn đến độ dài 1 + 2 + 6 = 9. Đối với n = 4, bạn nhận được 33. Và đối với n = 5, bạn nhận được 153, tương ứng với siêu hoán vị ngắn nhất trong mỗi trường hợp.
Tuy nhiên, đối với n lớn hơn, thuật toán này không còn áp dụng: máy tính đã có thể tìm thấy các siêu hoán vị ngắn hơn so với những gì nó gợi ý. Trên thực tế, công thức 1! + 2! + 3! + ... + n! ước tính quá cao độ dài của siêu hoán vị ngắn nhất đối với n lớn. Mặc dù thuật toán chỉ đưa ra một câu trả lời gần đúng, các nhà toán học sử dụng nó làm điểm khởi đầu, với mục tiêu thu hẹp các lựa chọn để tìm ra câu trả lời chính xác hơn.
Năm 2013, Nathaniel Johnston, hiện là giáo sư toán học tại Đại học Mount Allison ở New Brunswick, đã tìm thấy một trang fandom của Melancholy of Haruhi Suzumiya. Bản thân Johnston không phải là một fan hâm mộ anime. Anh đã đến trang web sau khi tìm kiếm một số thuật ngữ liên quan đến siêu hoán vị. Ở đó, anh đã bắt gặp cuộc thảo luận đã được tổ chức trên 4chan gần hai năm trước đó, mà một người dùng đã sao chép vào trang fandom.
Johnston đã không bận tâm đến việc tính toán mà đã trích dẫn bài đăng trên fandom trên blog của mình. Bình luận này cũng không được chú ý trong vài năm. Sau đó, vào tháng 10 năm 2018, nhà toán học Robin Houston đã tình cờ thấy bài đăng trên blog của đồng nghiệp của mình thông qua một sự trùng hợp kỳ lạ. Houston vừa mới biết rằng tác giả khoa học viễn tưởng người Úc Greg Egan đã tìm thấy độ dài tối đa mới cho các siêu hoán vị ngắn nhất, được biểu thị là:
n! +(n –1)! + (n – 2)! + (n – 3)! + n – 3
Điều đó tự nó đã kỳ lạ. Nhưng khi Houston bắt đầu tìm hiểu thêm về kết quả này, anh nhận ra rằng độ dài tối thiểu của một siêu hoán vị đã được một người dùng ẩn danh của fandom anime đưa ra một giá trị mới (anh không biết về nguồn gốc trên 4chan vào thời điểm đó). Công thức cho độ dài tối thiểu là:
n! +(n – 1)! + (n – 2)! + n – 3
Houston đã chia sẻ khám phá của mình trên Twitter (nay là X) vào ngày 23 tháng 10 năm đó. "Một tình huống kỳ lạ. Giới hạn dưới tốt nhất được biết đến cho độ dài tối thiểu của siêu hoán vị đã được chứng minh bởi một người dùng ẩn danh của một wiki chủ yếu dành cho anime," anh viết.
Cùng với các đồng nghiệp của mình, các nhà toán học Jay Pantone và Vince Vatter, Houston đã quyết định kiểm tra bằng chứng của người dùng 4chan và viết nó ra một cách toán học. Các nhà nghiên cứu đã đăng công trình toán học của họ lên Bách khoa toàn thư trực tuyến về dãy số nguyên trong cùng tháng đó, và tác giả đầu tiên được liệt kê là "Người đăng ẩn danh 4chan."
Vậy những công thức này cho chúng ta biết điều gì? Nếu bạn muốn xem tất cả các tập của một bộ phim gồm n phần theo tất cả các kết hợp có thể, bạn phải xem ít nhất n! +(n – 1)! + (n – 2)! + n – 3 tập—đó là đóng góp của người dùng 4chan—và nhiều nhất là n! +(n – 1)! + (n – 2)! + (n – 3)! + n – 3, điều mà chúng ta biết thông qua công trình của Egan.
Trong trường hợp của series tám tập Kaleidoscope, bạn sẽ phải xem ít nhất 46.085 tập và nhiều nhất là 46.205 tập. Đối với The Melancholy of Haruhi Suzumiya có 14 tập, con số tăng lên đáng kể: tối thiểu 93.884.313.611 tập và tối đa 93.924.230.411. Hãy nhớ rằng đây không phải là một giải pháp hoàn chỉnh—nó chỉ đặt ra một phạm vi cho kích thước của một siêu hoán vị cho phép bạn xem phim một cách hiệu quả theo mọi thứ tự có thể.
May mắn thay, Egan cũng cung cấp một thuật toán để xây dựng siêu hoán vị tương ứng. Điều này cho phép người hâm mộ Haruhi tìm ra thứ tự xem các tập tốt nhất. Nhưng với thời lượng trung bình của một tập là khoảng 24 phút, sẽ mất khoảng 4 triệu năm để xem hết siêu hoán vị này.
Từ diễn đàn anime 4chan đến bài toán "siêu hoán vị" gây sốt giới toán học
Các giải pháp toán học có thể được tìm thấy ở những nơi đáng ngạc nhiên, bao gồm cả thế giới ngầm của Internet. Vào năm 2011, một người dùng ẩn danh trên diễn đàn hình ảnh 4chan đã đặt ra một câu đố toán học về bộ anime kinh điển The Melancholy of Haruhi Suzumiya. Mặc dù diễn đàn này tràn ngập...
