537 BILANGAN, ENAM WARNA, TANPA JUMLAH

Inilah teka-teki yang bisa dipahami anak-anak. Ambil bilangan 1, 2, 3, dan seterusnya. Beri masing-masing sebuah warna. Satu-satunya aturan: dalam satu warna, kamu tidak boleh menemukan dua bilangan bersama dengan jumlahnya. Kedua bilangan itu bahkan boleh sama, jadi jika 2 berwarna merah, maka 4 tidak boleh merah, karena 2 + 2 = 4.

Himpunan yang tidak memuat trio semacam itu disebut bebas-jumlah (sum-free). Seberapa jauh kamu bisa melangkah sebelum aturan itu memaksamu berhenti? Batas itu, untuk k warna, adalah bilangan Schur S(k). Masalah ini berawal dari makalah tahun 1916 karya I. Schur, entri pertama dalam daftar pustaka.

Barisan yang terkenal membandel

Dengan satu warna, kamu langsung macet: 1 + 1 = 2, jadi warna itu hanya bisa memuat bilangan 1. Nilai-nilai yang diketahui adalah:

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160, ditentukan oleh M. J. H. Heule (dalam makalah yang terbit pada 2018).

Untuk enam warna, tidak ada yang tahu jawabannya. Sejak 2000, konstruksi terbaik yang diketahui, ditemukan oleh H. Fredricksen dan M. M. Sweet lewat pencarian di antara pewarnaan simetris, mencapai 536. Angka itu sejak saat itu dikutip sebagai batas bawah terbaik — sebuah lantai: S(6) setidaknya sebesar itu, dan nilai sebenarnya, yang masih belum diketahui, bisa saja lebih tinggi.

Satu bilangan lagi

Zhiyang Chen dan Fan Long, dari University of Toronto, serta Ligeng Zhu, dari NVIDIA Research, kini mendorongnya ke 537. Bukti mereka adalah jenis yang disukai matematikawan karena keterusterangannya: mereka mencetak jawabannya. Enam daftar bilangan — berisi 76, 76, 88, 70, 76, dan 151 bilangan — yang bersama-sama memuat setiap bilangan bulat dari 1 sampai 537 tepat satu kali, tanpa satu warna pun yang memuat x, y, dan x + y. Memeriksanya berarti menguji setiap penjumlahan di dalam setiap daftar, pekerjaan singkat bagi komputer.

Solusinya punya bentuk yang mencolok. Ia simetris: setiap bilangan x berwarna sama dengan 538 − x. Empat warna pertama dimulai dari 1, 2, 3, dan 4; warna kelima baru muncul mulai 38, warna keenam baru mulai 151, dan warna keenam mengisi seluruh bentangan tengah dari 237 sampai 301. Bahkan warna pertama bisa dibangun ulang dari benih yang hanya berisi 14 bilangan kecil, dengan satu pencerminan, satu pergeseran, dan satu bilangan tambahan.

Riak yang merambat ke atas

Bilangan-bilangan Schur saling memengaruhi. Resep yang sudah dikenal mengubah pewarnaan yang baik dengan k warna menjadi pewarnaan dengan k + 2 atau k + 5 warna: S(k + 2) setidaknya 10 S(k) + 2, dan S(k + 5) setidaknya 380 S(k) + 148. Jadi, angka 537 yang baru ini mengangkat rekor-rekor lain:

• delapan warna: dari 5.362 menjadi 5.372 — dan tim juga membangun pewarnaan itu secara eksplisit;
• sebelas warna: dari 203.828 menjadi 204.208;
• tiga belas warna: dari 2.038.282 menjadi 2.042.082.

Ini juga memperbaiki sebuah bilangan Ramsey, R₆(3): jumlah titik terkecil, yang semuanya saling terhubung berpasangan, sehingga setiap pewarnaan sambungannya dengan enam warna pasti memuat segitiga satu warna. Beri nomor 538 titik dari 0 sampai 537 dan warnai sambungan antara i dan j dengan warna selisihnya |i − j|: pewarnaan bebas-jumlah itu tidak menyisakan satu pun segitiga satu warna. Jadi R₆(3) setidaknya 539, naik dari 538.

131 cara untuk melakukannya

Pencarian ini tidak menemukan satu solusi, tetapi 131 solusi yang benar-benar berbeda, yang oleh para penulis dikelompokkan ke dalam lima keluarga dan diterbitkan lengkap. Sebagian besar sangat mirip dengan solusi pertama: yang termasuk keluarga F1 sampai F4 sama dengannya di setidaknya 462 dari 537 posisi. Satu keluarga mematahkan simetri cermin; keluarga lain dibangun dengan mencampur tiga salinan acak dari aslinya.

Makalah ini tidak menjelaskan bagaimana pencarian itu sendiri dijalankan. Para penulis menekankan bahwa 131 pewarnaan mereka bukan katalog lengkap solusi enam warna, melainkan titik awal baru bagi siapa saja yang ingin mencoba mencapai 538.