Masalah 'Lonely Runner' Tampak Sederhana Saja

Versi aslinya dari cerita ini muncul di Majalah Kuanta.

Bayangkan sebuah latihan yang aneh: Sekelompok pelari mulai jogging mengelilingi lintasan melingkar, dengan masing-masing pelari mempertahankan kecepatan yang unik dan konstan. Akankah setiap pelari berakhir “kesepian”, atau relatif jauh dari orang lain, setidaknya satu kali, berapa pun kecepatannya?

Para ahli matematika menduga jawabannya adalah ya.

Masalah “pelari yang kesepian” mungkin tampak sederhana dan tidak penting, namun masalah ini sering muncul dalam berbagai bentuk dalam matematika. Ini setara dengan pertanyaan dalam teori bilangan, geometri, teori grafik, dan banyak lagi—tentang kapan kita bisa mendapatkan garis pandang yang jelas di bidang rintangan, atau di mana bola bilyar bisa bergerak di atas meja, atau bagaimana mengatur jaringan. “Ini memiliki banyak aspek. Ini menyentuh banyak bidang matematika yang berbeda,” katanya Matias Beck dari Universitas Negeri San Francisco.

Untuk dua atau tiga pelari saja, bukti dugaan tersebut bersifat mendasar. Matematikawan membuktikannya kepada empat pelari pada tahun 1970an, dan pada tahun 2007, mereka berhasil mendapatkan sejauh tujuh. Namun selama dua dekade terakhir, belum ada yang mampu mencapai kemajuan lebih jauh.

Lalu tahun lalu, Matthieu Rosenfeldseorang ahli matematika di Laboratorium Ilmu Komputer, Robotika, dan Mikroelektronika Montpellier, menyelesaikan dugaan untuk delapan pelari. Dan dalam beberapa minggu, seorang sarjana tahun kedua di Universitas Oxford bernama Tanupat (Paul) Trakulthongchai dibangun berdasarkan ide Rosenfeld untuk membuktikannya sembilan dan 10 pelari.

Kemajuan yang tiba-tiba ini telah memperbarui minat terhadap masalah ini. “Ini benar-benar sebuah lompatan kuantum,” kata Beck, yang tidak terlibat dalam pekerjaan tersebut. Menambahkan hanya satu pelari membuat tugas untuk membuktikan dugaan tersebut “jauh lebih sulit,” katanya. “Berubah dari tujuh pelari menjadi sekarang 10 pelari adalah hal yang luar biasa.”

Tanda hubung Awal

Pada awalnya, masalah pelari kesepian tidak ada hubungannya dengan lari.

Sebaliknya, para matematikawan tertarik pada masalah yang tampaknya tidak berhubungan: bagaimana menggunakan pecahan untuk memperkirakan bilangan irasional seperti pi, sebuah tugas yang memiliki banyak penerapan. Pada tahun 1960-an, seorang mahasiswa pascasarjana bernama Jorg M. Wills menduga itu metode berusia satu abad untuk melakukan hal tersebut sudah optimal—tidak ada cara untuk memperbaikinya.

Pada tahun 1998, sekelompok ahli matematika menulis ulang dugaan itu dalam bahasa lari. Mengatakan N pelari memulai dari tempat yang sama pada lintasan melingkar yang panjangnya 1 satuan, dan masing-masing berlari dengan kecepatan konstan yang berbeda. Dugaan Wills sama dengan mengatakan bahwa setiap pelari akan selalu merasa kesepian pada suatu saat, berapa pun kecepatan pelari lainnya. Lebih tepatnya, setiap pelari pada suatu saat akan menemukan dirinya berada pada jarak paling sedikit 1/N dari pelari lainnya.

Ketika Wills melihat makalah yang berisi pelari kesepian, dia mengirim email ke salah satu penulisnya, Luis Goddyn dari Universitas Simon Fraser, untuk mengucapkan selamat kepadanya atas “nama yang indah dan puitis ini.” (Jawaban Goddyn: “Oh, kamu masih hidup.”)

Matematikawan juga menunjukkan bahwa masalah pelari kesepian setara dengan pertanyaan lain. Bayangkan selembar kertas grafik yang tak terbatas. Di tengah setiap kotak, tempatkan sebuah kotak kecil. Kemudian mulailah dari salah satu sudut grid dan buat garis lurus. (Garis dapat menunjuk ke arah mana pun selain vertikal atau horizontal sempurna.) Berapa besar persegi yang lebih kecil sebelum garis harus mengenai salah satunya?

Ketika versi masalah pelari kesepian berkembang biak di seluruh matematika, minat terhadap pertanyaan tersebut meningkat. Matematikawan membuktikan kasus dugaan yang berbeda dengan menggunakan teknik yang sangat berbeda. Terkadang mereka mengandalkan alat dari teori bilangan; di lain waktu mereka beralih ke teori geometri atau grafik.

Namun hal ini berarti mereka tidak memiliki strategi umum mengenai cara mengatasi masalah tersebut. Sebaliknya, mereka memiliki banyak teknik cerdik namun bersifat ad hoc yang mungkin berhasil untuk empat pelari, katakanlah, tetapi tidak untuk lima pelari. Dengan setiap tambahan pelari, mereka harus kembali ke garis start.

Pada pertengahan tahun 2000-an, para ahli matematika telah membuktikan bahwa ketika ada tujuh atau kurang pelari yang berlari mengelilingi sebuah lintasan, masing-masing dari mereka pada akhirnya akan merasa kesepian. Mereka juga menemukan cara untuk menyederhanakan masalah. Misalnya, mereka menyadari bahwa mereka tidak perlu membuktikan dugaan untuk semua (banyak sekali) kombinasi kecepatan. Sebaliknya, jika mereka dapat menunjukkan bahwa hal tersebut benar untuk kombinasi apa pun kecepatan bilangan bulathal itu harusnya benar secara umum; mereka bisa mengabaikan pecahan dan irasional.

Ini adalah tugas yang jauh lebih mudah, namun tetap melibatkan penanganan kemungkinan kecepatan yang tak terhingga banyaknya. Dibutuhkan sesuatu yang lebih.

Batas Kecepatan

Pada tahun 2015, Terence Tao dari Universitas California, Los Angeles menanam benih pertama. Dia menunjukkan bahwa jika dugaan pelari kesepian berlaku untuk kecepatan yang relatif rendah, maka dugaan itu juga berlaku untuk kecepatan tinggi. Untuk sejumlah pelari tertentu, ahli matematika hanya perlu mempertimbangkan kecepatan bilangan bulat hingga ambang batas tertentu.

Hal ini mengurangi permasalahan menjadi jumlah perhitungan yang terbatas—setidaknya secara teori. Dalam praktiknya, bahkan ketika Anda hanya berhadapan dengan beberapa pelari, jumlah kombinasi kecepatan yang harus Anda periksa masih “astronomis dan sama sekali tidak praktis,” kata Nuh Kravitz dari Universitas Oxford.

Kemajuan Tao pada akhirnya menarik perhatian Rosenfeld, yang tertarik pada pembuktian yang menggunakan komputer untuk memeriksa banyak contoh.

Dia menyusun ulang masalahnya dengan mempertimbangkan kemungkinan contoh tandingan dari dugaan tersebut: Ciri-ciri apa yang harus dimiliki oleh kecepatan pelari agar setidaknya satu pelari tidak akan pernah sendirian?

Ternyata kecepatan mereka harus dibatasi secara ketat. Rosenfeld menggunakan program komputer, bersama dengan ide-ide dari teori bilangan, untuk menunjukkan bahwa jika dia mengalikan semua kecepatan, hasil kali kecepatannya harus habis dibagi dengan bilangan prima tertentu. Kini yang perlu ia lakukan hanyalah membuktikan bahwa tidak ada kombinasi kecepatan yang dapat memenuhi kondisi ini.

Untuk melakukannya, dia kembali ke versi ambang batas Tao yang dimodifikasi. Dia kemudian menuliskannya kembali dalam bentuk perkalian kecepatan: Jika dugaan pelari kesepian itu benar untuk produk dengan ukuran tertentu, maka dugaan itu secara umum pasti benar. Hal ini menyiratkan bahwa jika dugaan tersebut salah, contoh tandingan dapat ditemukan dengan hasil kali di bawah ambang batas.

Namun Rosenfeld telah menunjukkan bahwa dalam contoh tandingan apa pun, hasil kali harus habis dibagi semua bilangan prima tersebut. Produk seperti itu harus berukuran besar. Faktanya, begitu besar sehingga jauh melampaui ambang batas.

Dengan kata lain, tidak ada contoh tandingan terhadap dugaan pelari kesepian—setidaknya, tidak untuk delapan pelari. Dugaan itu benar.

Keluar Jalur

Rosenfeld mulai memikirkan bagaimana memperluas pembuktiannya ke sembilan pelari. Sementara itu, Kravitz melihat makalah Rosenfeld dan menunjukkannya kepada seorang sarjana menjanjikan yang pernah dia bimbing di Oxford, Paul Trakulthongchai. Dia menyarankan Trakulthongchai untuk mengerjakan dugaan untuk sembilan pelari.

Trakulthongchai menggunakan pendekatan Rosenfeld secara keseluruhan, namun ia mengembangkan teknik komputasi yang lebih efisien untuk menunjukkan dengan tepat pembagi prima yang harus dimiliki oleh sebuah contoh tandingan. Hal ini memungkinkan dia untuk lebih cepat mengesampingkan semua contoh tandingan sembilan dan 10 pelari: Dugaan itu benar dalam kedua kasus. (Rosenfeld secara independen juga membuktikan dugaan tersebut kepada sembilan pelari, hanya beberapa hari setelah Trakulthongchai melakukannya. Dia senang melihat kemajuan matematikawan lainnya. Namun “di saat yang sama, saya sedikit kecewa,” katanya sambil tertawa.)

Metode Rosenfeld dan Trakulthongchai terlalu mahal secara komputasi untuk digunakan oleh lebih banyak pelari, sehingga membuat mereka terjebak pada kasus masalah berikutnya. “Untuk mencapai 11, saya pikir Anda memerlukan cara pandang yang benar-benar baru,” kata Trakulthongchai.

Namun para ahli matematika sangat antusias dengan kemajuan terkini ini—dan fakta bahwa satu pendekatan dapat menyelesaikan tiga kasus sekaligus, padahal sebelumnya setiap kasus baru memerlukan bukti yang benar-benar baru. “Saya benar-benar melihat cara baru untuk memahami keseluruhan dugaan melalui ide baru ini,” katanya Matthias Schymura dari Universitas Rostock di Jerman.

Meskipun bukti keseluruhan dugaan tersebut masih terasa jauh dari kenyataan—dan para ahli matematika belum sepakat apakah dugaan tersebut akan berlaku pada kasus apa pun. N pelari— “segala sesuatunya mulai bergerak setelah tidak bergerak selama beberapa saat,” kata Kravitz.

Terinspirasi oleh hasil baru, Schymura dan yang lainnya mengorganisir a lokakarya tentang dugaan pelari kesepianyang akan diadakan di Rostock pada bulan Oktober ini. Ini akan mempertemukan para peneliti dari berbagai bidang di mana dugaan tersebut muncul. Harapannya adalah mereka akan mendekati masalah ini dari berbagai sudut pandang dan “mengkomunikasikan serta menjembatani berbagai bidang,” kata Schymura, untuk menemukan bukti potensial atau contoh tandingan.

“Saya yakin masalah ini akan terpecahkan,” kata Wills. “Tapi mungkin butuh sekitar 20, 30 tahun lagi.”

Cerita asli dicetak ulang dengan izin dari Majalah Kuantasebuah publikasi independen secara editorial dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman masyarakat terhadap sains dengan meliput perkembangan dan tren penelitian di bidang matematika serta ilmu fisika dan kehidupan.