JUMLAH TERBESAR YANG TAK BISA DIBAYAR, KINI DIBATASI DENGAN KETAT

Bayangkan sebuah mesin kasir yang hanya menerima beberapa jenis koin, dalam jumlah tak terbatas, dan tidak pernah memberi kembalian. Sebagian jumlah bisa dibayar dengan pas; sebagian lagi tidak akan pernah bisa. Matematikawan menyebut nilai-nilai koin itu pembangkit (generators), dan mengajukan pertanyaan yang tampak sederhana tetapi menipu: berapa jumlah terbesar yang tidak bisa dibayar?

Jumlah yang tak akan pernah bisa dibayar

Ambil bilangan bulat a₁ < a₂ < … < aₙ yang tidak memiliki faktor yang dimiliki bersama oleh semuanya. Total yang diperoleh dengan menjumlahkan bilangan-bilangan ini, masing-masing sebanyak yang Anda mau, disebut “terwakilkan” (representable). Hanya ada berhingga banyak bilangan bulat yang tidak terwakilkan; yang terbesar adalah bilangan Frobenius, F. (Jika salah satu nilai adalah 1, semua jumlah bisa dibayar dan F ditetapkan −1.)

Contoh kecil: dengan koin 3, 4, dan 6, Anda bisa membayar 3, 4, 6, 7, 8, dan setiap jumlah sesudahnya, tetapi tidak pernah 1, 2, atau 5. Jadi F = 5. Perhatikan bahwa 3 dan 6 memiliki faktor bersama; yang penting adalah tidak ada faktor yang dimiliki bersama oleh ketiganya.

Untuk dua koin ada jawaban pasti, rumus Sylvester: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Untuk tiga atau lebih, pekerjaannya adalah membatasi F: membuktikan bahwa F tidak bisa melebihi suatu nilai yang dihitung dari koin-koin itu.

Faktor 2 yang membandel

Paul Erdős dan Ronald Graham membuktikan, untuk tiga pembangkit atau lebih:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Di sini aₙ adalah nilai terbesar, aₙ₋₁ nilai terbesar kedua, n banyaknya nilai, dan ⌊ ⌋ berarti pembulatan ke bawah. Seperti rumus Sylvester, rumus ini melibatkan dua koin terbesar.

Mereka juga memperkirakan kasus terburuk, yaitu F terbesar yang mungkin ketika semua n nilai paling besar t. Selisih antara perkiraan-perkiraan mereka, kira-kira faktor 2, memunculkan sebuah konjektur yang tercatat sebagai Soal Erdős #433. Jacques Dixmier menyelesaikannya, dan juga membuktikan batas yang lebih sederhana yang berlaku untuk setiap himpunan: F ≤ aₙ²/(n − 1). Faktor 2 hilang, tetapi koin terbesar kedua juga ikut hilang.

Mempertahankan kedua koin terbesar

Lin Chen, Tingwei Hu, Yuchen Mao, dan Guochuan Zhang, dari Fakultas Ilmu dan Teknologi Komputer Universitas Zhejiang, menginginkan keduanya: tanpa faktor 2, dan koin terbesar kedua tetap dipertahankan. Jawaban mereka, yang berlaku untuk setiap himpunan dengan dua nilai atau lebih:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Di sini ⌈ ⌉ berarti pembulatan ke atas. Dibandingkan dengan Erdős dan Graham, faktor 2 telah lenyap, dengan harga membagi dengan n − 1 alih-alih n dan membulatkan ke atas. Dibandingkan dengan Dixmier, batas baru ini bisa jauh lebih kecil ketika koin terbesar kedua kecil dibandingkan koin terbesar.

Pada contoh 3, 4, 6, batas Erdős dan Graham memberikan 10, batas Dixmier 18, dan batas baru 4 × 3 − 6 − 1 = 5, tepat nilai sebenarnya. Ini tidak mengejutkan: himpunan ini termasuk keluarga kasus ekstrem yang dijelaskan di bawah, yang dibangun untuk mencapai batas itu dengan tepat; makalah ini tidak memberikan perbandingan pada himpunan yang umum.

Memilah jumlah berdasarkan sisa

Buktinya mengikuti jalur Erdős dan Graham. Pilah setiap jumlah berdasarkan sisanya setelah dibagi dengan koin terbesar, aₙ. Begitu suatu jumlahan koin-koin yang lebih kecil mencapai sisa tertentu, menambahkan salinan aₙ akan mencapai setiap jumlah yang lebih besar dengan sisa yang sama. Tugasnya adalah menunjukkan bahwa setiap sisa bisa dicapai dengan murah.

Alat kuncinya adalah teorema Kneser, tentang seberapa besar suatu himpunan jumlahan pasti berukuran. Erdős dan Graham memakainya untuk menunjukkan bahwa jumlahan dari sekitar aₙ/n koin mencakup lebih dari separuh sisa, lalu menggandakannya untuk mencakup semuanya. Setiap koin dalam jumlahan ini bernilai paling banyak aₙ₋₁, jadi menggandakan banyaknya koin menggandakan biayanya: dari situlah faktor 2 berasal.

Bukti baru memakai jumlahan dari ⌈aₙ/(n − 1)⌉ koin. Ketika jumlahan ini melewatkan beberapa sisa, teorema Kneser mengatakan bahwa sisa yang terlewat tidak tersebar acak: mereka membentuk keluarga-keluarga sisa utuh yang berjarak teratur. Makin banyak keluarga yang terlewat, makin banyak koin kecil yang harus berjejal ke setiap keluarga yang tercapai, sehingga setiap keluarga itu berisi beberapa koin kecil, dan beberapa koin tambahan yang diperlukan untuk mencapai keluarga yang terlewat menjadi murah. Totalnya tidak pernah melebihi ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Langkah pertama itu memberikan batas tanpa “− 1” di ujungnya. Satu satuan terakhir datang dari argumen terpisah, berdasarkan teorema Scherk dan Kemperman tentang jumlahan yang hanya bisa dibentuk dengan satu cara: argumen ini menunjukkan bahwa jumlah di ambang batas, aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ, sendiri selalu bisa dibayar. Menurut bagian ucapan terima kasih, para penulis lebih dulu membuktikan batas yang lebih lemah; GPT-6 kemudian membantu menemukan argumen yang menurunkannya satu satuan, dan juga membantu dalam bukti bahwa batas itu tidak bisa diturunkan serta dalam penyuntingan bahasa Inggrisnya. Para penulis menyatakan bahwa mereka bertanggung jawab atas naskah akhir.

Kasus yang tepat menyentuh batas

Batas ini tidak bisa diturunkan: untuk setiap n ≥ 3, para penulis membangun tak terhingga banyaknya himpunan yang F-nya tepat sama dengan batas itu. Ambil sembarang q ≥ 2 dan nilai-nilai q, 2q, …, (n − 1)q, ditambah (n − 2)q + 1. Semua kecuali satu adalah kelipatan q, jadi mereka tidak bisa membayar apa pun yang tidak bisa dibayar q sendirian. Himpunan ini berperilaku seperti dua koin, q dan (n − 2)q + 1, dan rumus Sylvester memberikan F yang tepat sama dengan batas baru. Dengan n = 3 dan q = 3, resep ini menghasilkan persis contoh 3, 4, 6 di atas.

Lebih sedikit koin, plafon lebih rendah

Batas ini juga bisa dibaca dari sudut kerapatan. Ia berlaku untuk setiap himpunan tereduksi yang terdiri atas i nilai terkecil ditambah nilai terbesar, asalkan semuanya masih tidak punya faktor persekutuan. Membuang koin hanya bisa membuat pembayaran makin sulit, jadi plafon yang terbukti untuk himpunan tereduksi juga berlaku untuk himpunan lengkap. Yang mengendalikan hasilnya kira-kira adalah aᵢ/i, kebalikan dari seberapa rapat i nilai pertama mengisi bilangan dari 1 sampai aᵢ: kelompok yang paling rapat yang menang. Secara khusus, catat para penulis, koin terbesar kedua bisa begitu saja dikesampingkan selama koin-koin yang tersisa masih tidak punya faktor yang dimiliki bersama oleh semuanya.

Makalah ini murni teoretis: tidak ada angka tentang seberapa jauh lebih kecil batas baru ini pada himpunan koin yang umum, dan ketajamannya (bahwa batas ini tak bisa diturunkan) hanya terbukti untuk tiga nilai koin atau lebih.