♛ BIDAK RATU CATUR YANG MENGIKUTI RASIO EMAS

Ambil papan catur yang membentang tanpa akhir ke kanan dan ke atas. Letakkan satu ratu di sudut kiri bawah. Lalu geser satu kolom ke kanan dan letakkan ratu di petak terendah yang tidak diserang oleh ratu sebelumnya — tidak di baris yang sama, tidak di diagonal yang sama, tidak di antidiagonal yang sama. Ulangi, kolom demi kolom, selamanya.

Ini adalah aturan serakah (greedy): setiap ratu mengambil tempat kosong pertama tanpa perencanaan. Baris-baris yang dihasilkannya dimulai dengan 0, 2, 4, 1, 3, 8, 10, 12, 14, 5, 7, 18, 6, 21, 9… Tampak acak. Padahal tidak.

Dua puluh kolom pertama. Ratu hijau kebiruan berada di atas diagonal utama, ratu jingga di bawahnya. — Gambar 1, Ho (2026), arXiv:2609.31336.

Dua garis dan sebuah bilangan terkenal

Plot para ratu pada seratus kolom pertama, dan mereka jatuh pada dua garis lurus. Ratu di atas diagonal menanjak dengan kemiringan mendekati 1,618; yang di bawahnya, dengan kemiringan mendekati 0,618. Kedua angka itu terkait dengan rasio emas, φ = (1 + √5)/2: satu garis adalah y = xφ, yang lain y = x/φ.

Posisi ratu untuk 100 kolom pertama, pada sumbu berskala sama, dengan garis y = xφ dan y = x/φ. — Gambar 2, Ho (2026), arXiv:2609.31336.

Barisan ini sudah tercatat dalam On-Line Encyclopedia of Integer Sequences sejak 2001. Pada 2020, Michel Dekking, Jeffrey Shallit, dan Neil Sloane mengajukan konjektur bahwa para ratu tidak pernah menyimpang lebih dari jarak terbatas dari kedua garis ini. Donald Knuth memeriksanya secara numerik hingga satu miliar kolom. Belum ada yang membuktikannya.

Teoremanya

Boon Suan Ho dari National University of Singapore kini membuktikannya dengan batas yang eksplisit. Untuk setiap kolom n:

• ratu di atas diagonal berjarak kurang dari 5/φ ≈ 3,09 petak dari garis y = xφ;
• ratu di bawahnya berjarak kurang dari 4 + 5/φ ≈ 7,09 petak dari garis y = x/φ.

Mengapa rasio emas? Misalkan sebagian θ dari ratu berada di atas diagonal. Menghitung bagaimana kedua keluarga berbagi baris dan diagonal memaksa θ memenuhi θ² + θ = 1, yang solusi positifnya adalah 1/φ. Kesulitan sebenarnya adalah menunjukkan bahwa galatnya tidak pernah membesar. Semuanya bermuara pada satu lema kunci: ratu ke-j di bawah diagonal selalu berada dalam jarak 4 diagonal dari diagonal bawah ke-j.

Bukti yang diperiksa mesin

Untuk membuktikan lema itu, Ho menggambarkan papan sebelum setiap kolom dengan sebuah “keadaan lokal” kecil: beberapa angka ditambah kata-kata pendek dalam alfabet empat huruf yang mencatat letak ratu-ratu yang tinggi. Sebuah “graf riwayat” berhingga dari kata-kata 12 huruf (2.092 simpul, 2.603 sisi) menentukan huruf mana yang boleh mengikuti huruf mana. Komputer lalu menjelajahi setiap keadaan yang dapat dicapai dari kolom 30: 7.014 keadaan, semuanya memenuhi batas yang disyaratkan. Sebuah induksi menunjukkan bahwa barisan sebenarnya tidak pernah keluar dari himpunan berhingga ini.

Dua program independen, tanpa berbagi kode sedikit pun, mencapai keadaan-keadaan yang sama. Formalisasi dalam asisten pembuktian Lean menyertai makalah ini, dan semua kodenya terbuka untuk umum.

Bonus: sebuah permainan dan generator cepat

Para ratu menyimpan sebuah permainan. Gerakkan satu ratu ke kiri, ke bawah, atau secara diagonal ke arah kiri; siapa yang tidak bisa bergerak, kalah. Petak-petak yang kalah tepat merupakan ratu-ratu serakah itu. Hilangkan gerakan antidiagonal, dan Anda mendapatkan Nim Wythoff, permainan yang sudah dikenal diatur oleh rasio emas.

Bukti ini juga menghasilkan algoritma yang luar biasa hemat. Program Ho menghasilkan sepuluh miliar ratu dalam sekitar 25 detik dengan memori 1,76 megabita, dibandingkan 49 detik dan lebih dari 6 gigabita untuk adaptasi program Knuth. Ternyata, setiap diagonal papan memuat tepat satu ratu.

Ditemukan dengan AI

Makalah ini diakhiri dengan sebuah pernyataan: “Bukti ini ditemukan dengan GPT-6 Pro, yang juga menghasilkan draf awal makalah ini.” Makalah itu kemudian direvisi dengan Claude Opus 5.5 di bawah arahan penulis. Satu pertanyaan masih terbuka: batas bawah Knuth yang lebih ketat, yang dikonfirmasi komputer hingga seratus miliar kolom, masih menunggu bukti.