Tugas 165 tahun yang lalu menghantui matematikawan

Pada tahun 1850, Pdt. Thomas Kirkman, seorang matematikawan dan rektor paroki di Lancashire, merumuskan sebuah teka-teki yang kelihatan tidak bersalah di sebuah majalah hiburan untuk pecinta matematika “Notebook for Ladies and Gentlemen”:

“Lima belas anak sekolah muda pergi jalan-jalan selama tujuh hari dalam tiga baris: Anda perlu mengatur setiap hari "sehingga pasangan siswi yang sama tidak pernah bertemu dua kali di baris yang sama."

Tugasnya terlihat sederhana, tetapi jika Anda mencoba menyelesaikannya, Anda segera menyadari bahwa ini tidak benar. Anda dapat mencoba menyelesaikannya dengan pensil dan kertas atau bermain dalam versi HTML .

Karena kesederhanaannya yang salah, tugas itu dengan cepat menjadi terkenal. Pecinta matematika mengirim keputusan mereka, dan para ilmuwan menerbitkan artikel ilmiah dengan upaya merumuskan solusi umum untuk masalah tersebut.

Akibatnya, teka-teki ini membantu membentuk bidang matematika baru: skema kombinatorial , yang sekarang dikhususkan untuk buku teks tebal .. Apa yang dimulai sebagai tugas sederhana untuk mendistribusikan orang ke dalam kelompok (atau skema, sebagaimana mereka akhirnya disebut) kini telah menjadi metode yang digunakan dalam desain eksperimental, kode koreksi kesalahan dalam ilmu komputer, kriptografi, pertanian, olahraga, dan bahkan dalam penipuan judi. (Ada cerita ketika seorang kartel kriminal memperoleh jutaan dolar dalam tujuh tahun dengan membeli tiket dengan semua kemungkinan kombinasi 5 dari 46 dalam lotere 6 dari 46 jika biaya tiket lebih rendah daripada bonus tambahan untuk memenangkan 5 dari 46 ditambah kemungkinan memenangkan jackpot).

Misalnya, kode Hamming klasik untuk menyelesaikan kesalahan menggunakan solusi masalah tentang siswi (membuat kelompok yang terdiri dari tiga siswi, di mana tidak ada pasangan yang diulang), tetapi hanya untuk skema tujuh gadis (bit).


Pesawat Fano untuk (7, 3, 2)

Yang paling mengejutkan, selama 165 tahun, matematikawan belum mampu menyelesaikan masalah secara umum. Mereka masih belum bisa memberikan jawaban, apa adalah solusi untuk teka-teki di bawah kondisi awal: ada n siswi, Anda perlu membuat kelompok ukuran k , sehingga set t gadis belum pernah bertemu dua kali dalam kelompok yang sama. Formulasi seperti itu disebut skema (n, k, t) .

Misalnya, untuk kelompok yang terdiri dari 19 anak perempuan, ada lebih dari 11 miliar kemungkinan kembar tiga di mana setiap pasangan bertemu hanya sekali. Nomor ini adalah jawabannya. Tetapi jumlah opsi tumbuh secara eksponensial dengan peningkatan jumlah siswi.

Jelas bahwa masalahnya diselesaikan dalam kondisi tertentu dan tidak diselesaikan dalam beberapa kondisi lain. Misalnya, jika kembar tiga dari semua pasangan yang mungkin terdiri dari enam siswi, masalahnya jelas tidak terpecahkan (ada lima pasangan yang mungkin dengan siswi Anya, pada saat yang sama, masing-masing kembar tiga memiliki dua pasangan dengan Anya, dan lima tidak dibagi menjadi dua). Artinya, menurut prinsip pembagian, banyak opsi (n, k, t) dihilangkan segera .

Pada saat yang sama, ada (n, k, t) yang sepenuhnya mematuhi prinsip pembagian, tetapi masih tidak memiliki solusi: misalnya, (47, 3, 2) .

Selama beberapa tahun terakhir, solusinya telah dikenal untuk banyak kombinasi (n, k, t)yang diperiksa secara aljabar atau dengan kekerasan pada komputer. Tetapi bagaimana cara menyelesaikannya secara umum, apa yang harus dilakukan dengan pengecualian seperti (47, 3, 2) ? Bagaimana memahami apakah suatu masalah memiliki solusi atau tidak?

Tugas ini telah lama dianggap sebagai salah satu masalah yang paling terkenal dalam kombinatorik, kata ahli matematika Gil Kalai dari Universitas Ibrani di Yerusalem dalam sebuah wawancara dengan Wired. Dia ingat bagaimana dia berdebat dengan rekannya tentang hal ini satu setengah tahun yang lalu, dan mereka sampai pada kesimpulan bahwa "kita tidak akan pernah tahu jawabannya, karena tugasnya jelas terlalu rumit."

Namun, hanya dua minggu kemudian, profesor matematika muda Peter Keevash dari Oxford membuktikan bahwa Kalai salah. Dalam sebuah artikel ilmiahdari Januari 2014, ia berpendapat bahwa solusi untuk masalah hampir selalu ada jika kondisi keterbagian terpenuhi. Dalam makalah baru bertanggal April 2015, ia menunjukkan cara menghitung perkiraan jumlah solusi untuk parameter yang diberikan.

Tidak ada teori probabilitas yang diharapkan untuk diterapkan pada solusi masalah, tetapi metode ini bekerja dengan sempurna.

Kembali ke lotere, scammers menyadari bahwa adalah mungkin untuk mengurangi jumlah tiket yang dibeli dengan membeli semua kombinasi 5 dari 46 (ketika menentukan 6 dari 46 angka), maka mereka akan menerima semua hadiah tambahan, dan mereka juga dapat menerima jackpot. Meskipun skema (46, 6, 5) belum dihitung, ada skema yang cukup dekat untuk aplikasi praktis. Salah satunya mungkin digunakan oleh kartel kriminal.

Jumlah sirkuit terhitung baru terus meningkat. Banyak dari mereka menemukan aplikasi praktis, seperti (15, 3, 2) dari masalah klasik, dan (46, 6, 5) . 1000 halaman panduan dengan diagram keluar. Namun, matematikawan masih bingung bagaimana menentukan apakah ada solusi untuk kondisi tertentu. Berkat Kivash, kami belajar bahwa kemungkinan ini cukup tinggi. Jadi setidaknya sekarang jelas bahwa dengan semua yang tidak diketahui, lebih baik mencari solusi daripada menolaknya. Selain itu, ada alat untuk menghasilkan rangkaian sampel untuk parameter apa pun.

Namun berkat karya Kivash, diharapkan metode yang dapat dikembangkan untuk membuat akuratskema untuk parameter apa pun. Jika ini terjadi, itu akan menjadi terobosan luar biasa dalam matematika.

Namun, karya Kivash adalah murni teoretis. Para ahli mengatakan bahwa membuat algoritma praktis berdasarkan metodenya akan membutuhkan kerja keras dari beberapa generasi ahli matematika.

Source: https://habr.com/ru/post/id380785/