Permasalahan Haruhi Suzumiya : Masalah Superpermutasi

Selain MC-nya bermasalah, anime ini memantik diskusi yang mendalam dalam dunia matematika.

The Melancholy of Haruhi Suzumiya (涼宮ハルヒの憂鬱, Suzumiya Haruhi no Yūutsu) adalah anime populer tahun 2006 yang diadaptasi oleh Kyoto Animation dari novel berjudul serupa. Serialnya terdiri dari 14 episode yang ditayangkan di televisi Jepang dari April hingga Juli 2006. Menariknya, penayangan episode-episode anime ini tidak berada dalam urutan waktu yang benar, jadi penonton perlu menalar sendiri urutan ceritanya.

Penayangan yang tidak berurutan ini membuat penonton yang iseng bertanya-tanya, Berapa banyak urutan minimum yang harus saya tonton agar saya dapat menonton semua episodenya dalam semua kemungkinan urutan?

Untuk memahami teka-teki ini, kita bisa mencoba kasus yang sederhana terlebih dahulu. Misalnya anime, katakanlah judulnya Wiro Sableng dengan 2 episode, hanya akan ada 2 kemungkinan permutasi:

Jika kita menonton anime tersebut dalam urutan episode 1, 2, lalu 2, lalu 1 lagi, kita telah menyelesaikan dua macam permutasi tersebut.

1	2	2	1
12		21

Ini disebut sebagai superpermutasi, yaitu susunan objek-objek yang mengandung semua permutasi yang mungkin dari objek-objek tersebut.

Superpermutasi: Susunan objek-objek yang mengandung semua permutasi yang mungkin dari objek-objek tersebut.

Kita mendapatkan semua permutasi 12 dan 21 tersebut dalam 4 kali menonton. Namun kalau kamu perhatikan, episode 2 ditonton dua kali berturut-turut. Jadi kita bisa menyederhanakan cara menontonnya, yaitu dengan urutan 3 episode saja, yaitu 121.

Superpermutasi menonton 2 episode: Di dalamnya mengandung urutan 1-2 dan 2-1.

1	2	1
12
	21

Dengan urutan 121, kamu sudah menonton kedua permutasi urutan tersebut sekaligus. Ini bukan satu-satunya urutan yang bisa dibuat. Kamu bisa menontonnya dengan urutan 212, tetapi kedua macam urutan ini sama-sama minimum. Urutan minimum kita bisa menonton semua permutasi sekaligus ini disebut sebagai superpermutasi minimum.

Alternatif lain urutan menonton 2 episode

2	1	2
21
	12

Jika anime tersebut memiliki 3 episode, berarti kemungkinan permutasinya:

123	132
213	231
312	321

Dengan urutan menonton 123121321 kita akan berhasil menonton semua kemungkinan permutasinya.

Superpermutasi untuk 3 episode

1	2	3	1	2	1	3	2	1
123				213
	231				132
		312				321

Bagaimana mendapatkannya?

Kita bisa menggambarkan hubungan antar permutasi menggunakan graf berarah seperti di bawah ini. Setiap permutasi yang memiliki akhiran dan awalan yang sama dihubungkan dengan tanda panah. Lalu panjang akhiran dan awalan yang sama tersebut menjadi bobot panah yang bersangkutan.

digraph { p123 -> p231 [dir=both, headlabel=2, taillabel=1]; p231 -> p312 [dir=both, headlabel=2, taillabel=1]; p312 -> p123 [dir=both, headlabel=2, taillabel=1]; p123 -> p321 [dir=both, label=1]; p213 -> p312 [dir=both, label=1]; p132 -> p231 [dir=both, label=1]; p132 -> p321 [dir=both, headlabel=2, taillabel=1]; p321 -> p213 [dir=both, headlabel=2, taillabel=1]; p213 -> p132 [dir=both, headlabel=2, taillabel=1]; }

Dengan demikian, terlihat bahwa akan lebih pendek jika kita menghubungkan 123 ke 231 (menjadi 1231) dibandingkan ke 321 (menjadi 12321). Jadi kita memprioritaskan untuk menggabungkan verteks yang dihubungkan panah dengan bobot 2.

Dari 123, 231, bisa dilanjutkan lagi dengan 312, karena panahnya masih memiliki bobot 2. Jadi sejauh ini sub-superpermutasinya adalah 12312. Namun kita tidak dapat melanjutkan lagi dengan cara yang sama, karena satu-satunya kemungkinan adalah melanjutkan dengan 123 yang berarti kembali seperti permutasi pertama.

Terlepas dari 12312, kita dapat memperoleh susunan lain dengan cara yang sama, dan hasilnya adalah 23123, 31231, 13213, 32132, dan 21321. Namun perhatikan juga bahwa keenam rangkaian ini bisa dikategorikan menjadi 2 macam:

Mengandung 123, 231, dan 312: 12312, 23123, 31231
Mengandung 132, 321, dan 213: 13213, 32132, 21321

Jadi kita cukup mempertimbangkan dua kelompok tersebut, dan mencari irisannya. Irisan terpanjang yang dapat diperoleh adalah 1 angka:

12312 dan 21321
23123 dan 32132
31231 dan 13213

Jadi kita tinggal menggabungkan keduanya menjadi rangkaian 9 angka (episode):

123121321
231232132
312313213

Permasalahan superpermutasi minimum ini disebut sebagai permasalahan Haruhi (Haruhi problem), sesuai nama anime yang memicu munculnya masalah ini. (Sesuai juga dengan karakter tokoh utamanya yang bermasalah.)

Sejauh artikel ini ditulis, belum ada pembuktian umum mengenai panjang superpermutasi minimum. Namun ada seseorang yang tidak diketahui namanya menulis pembuktian dalam situs 4chan mengenai batas bawah yang mungkin bagi superpermutasi minimum. Ia membuktikan bahwa untuk n \ge 2, panjang superpermutasi minimumnya paling sedikit adalah:

s(n) \ge n!+(n+1)!+(n+2)!+n-3

Rumus tersebut memberikan batas bawah panjang minimum superpermutasi. Artinya panjang superpermutasi minimumnya bisa di atas itu.

Pada tahun 2009, anime ini ditayangkan kembali di Jepang. Kali ini penayangannya disajikan secara kronologis dengan tambahan 14 episode lainnya. Namun memang dasar studio nyeleneh, di antara 14 episode tambahan tersebut ada 8 episode yang jalan ceritanya sama persis!

FEATURE: The Complete Guide on How to Watch The Melancholy of Haruhi Suzumiya

A lower bound on the length of the shortest superpattern

Teka-teki lain yang memantik diskusi mendalam dalam matematika adalah teka-teki jembatan Konigsberg.

Berikutnya: Referensi