Koleksi barang mana yang legal?
Menyebut kumpulan bidak catur (putih dan hitam) legal jika terjadi dalam posisi permainan catur legal. Misalnya KQRRBBNNPPPPPPPPkqrrbbnnppppppppadalah koleksi di awal permainan. Tampaknya setiap bagian dari ini (masih berisi dua raja) juga dimungkinkan. Tetapi terkadang Anda dapat memiliki banyak promosi, jadi misalnya Kkqqqqqqqqmungkin jika hitam mempromosikan kedelapan bidak kepada ratu sementara semua bidak lainnya ditangkap.
Koleksi barang mana yang legal?
Jawaban ini pada dugaan / status MathOverflow tanpa bukti bahwa kumpulan hukum adalah yang dapat diperoleh dari kumpulan awal menggunakan dua operasi berikut:
Hapus bidak (bukan raja) mana saja dan promosikan paling banyak satu bidak putih dan paling banyak satu bidak hitam.
Menghapus satu bidak dan mempromosikan paling banyak satu bidak berwarna sama dan paling banyak dua bidak berwarna berlawanan.
Apakah karakterisasi ini benar?
Jawaban
Ya, penokohannya benar, dan total ada 58.084.310 koleksi legal.
Untuk membuat kemajuan, kita membutuhkan tingkat wacana yang tepat, menghindari kehilangan akurasi sambil menghindari menyelam ke dalam hal-hal sepele.
Kebutuhan & kecukupan gerakan penghapusan
Ada dua jenis operasi yang disarankan & memadai untuk menjangkau semua koleksi legal:
(1) Delete a (non-K) officer & promote at most 1 wP and 1bP
(2) Delete a P & promote at most 1P of that color and at most 2Ps of the other color.
Pertama, dua kriteria itu perlu. Untuk membuka blokir file, pengambilan gambar harus dilakukan. Menangkap petugas akan memungkinkan kedua bidak dari file untuk dipromosikan. Bidak yang menangkap bidak dari berkas tetangga lebih efisien, karena memungkinkan tiga bidak untuk dipromosikan.
Syaratnya juga cukup, terlihat dengan membagi papan menjadi 4 pasang file. Kita harus membuat asumsi bahwa raja bisa menghindar dari aksi. Lihat nanti untuk contoh yang mengeksplorasi validitas asumsi ini.
"Permintaan persediaan"
Mungkin layak untuk beralih ke pertanyaan tentang koleksi mana yang dapat dicapai dengan cara ini:
- Hitung jumlah "petugas yang tidak memulai" yang terlihat untuk setiap sisi (ratu di luar yang pertama; petugas lain di luar yang kedua dari jenis itu): T_w & T_b
- Hitung jumlah "bidak awol" di setiap sisi: (bidak yang berubah menjadi NSO tidak dihitung): A_w & A_b
- Hitung jumlah "petugas hilang" untuk setiap sisi (ratu hilang, atau petugas lain kurang dari kedua jenis itu): M_w & M_b
Maka ketidaksetaraan "penawaran & permintaan" yang elegan berikut ini diperlukan dan kriteria yang memadai untuk koleksi legal:
M_b + 2*A_b >= N_w - M_w - A_w
M_w + 2*A_w >= N_b - M_b - A_b
Mengelompokkan istilah berdasarkan Putih & Hitam, sisi kiri adalah "penawaran", sisi kanan adalah "permintaan". Penawaran selalu non-negatif, jadi jika permintaan nol atau kurang, itu selalu terpenuhi. Demikian pula, pasokan 8+ akan memenuhi permintaan apa pun yang dapat terjadi.
Berikut contohnya. Bisakah kita memiliki 18 ratu di papan? Iya!
N_w = N_b = 8
(because 8 promoted pawns on each side)
A_w = A_b = 0
(every missing pawn was promoted)
M_w = M_b = 6
(all Rs, Bs & Ns were captured)
M_b + 2*A_b >= N_w - M_w - A_w
translates to:
6 + 2*0 >= 8 - 6 - 0
6 >= 2
Jadi ini legal. Demikian pula untuk pasokan Putih untuk permintaan Hitam. Bahkan jika kita memiliki kesatria yang masih di papan, jadi M_b = M_w = 4, pertidaksamaannya akan menjadi 4> = 4, jadi masih legal.
Selain mate / stalemate
Beberapa orang bertanya-tanya apakah posisi seperti itu dapat dicapai tanpa pasangan atau jalan buntu, yang merupakan pertanyaan yang wajar. Jawabannya iya. Ini seperti meminta untuk membuktikan bahwa 450 gram cornflake akan muat di dalam sebuah kotak. Ini adalah masalah pengalaman umum bahwa seseorang bisa mengguncang bungkusnya dan cornflake mengendap. Tidak terlalu banyak cornflake di dalam kotak. Meskipun jelas ilegal, dimungkinkan untuk mengatur raja dan hingga 34 (!) Ratu putih di papan tanpa pasangan atau kebuntuan yang membayangi. Pada kepadatan ini, itu menjadi agak ketat, tetapi eksperimen pemikiran ini menunjukkan bahwa ketika kita berurusan dengan hanya 18 ratu, di mana apalagi ratu yang ramah dapat melindungi dari musuh, ada banyak kelonggaran, dan tidak perlu khawatir tentang pasangan paksa. atau jalan buntu. Bahkan dengan 18 ratu, papan catur adalah sekotak cornflake yang sangat kosong :-)
Menghitung koleksinya
Mari fokus pada unit Putih dulu. Ada berapa banyak koleksi kulit putih legal yang ada? 8.694. Ini bukti singkatnya.
Misalkan k adalah jumlah promosi yang terlihat untuk benteng, ksatria atau uskup (yaitu perwira di luar pelengkap asli 2 untuk salah satu dari jenis ini). (Untuk alasan simetri, ratu dibahas dalam beberapa paragraf.)
Misalkan v (k) adalah banyaknya kombinasi yang berbeda dari R, N, B yang mencapai ini.
v(0) = 27:
because there may be 0-2 remaining of each of R,N,B.
For k>0, v(k) = (k^2 + 15*k + 38)/2
e.g.:
v(1) = again 27:
3 ways to pick one of R,N,B to be 3;
& 0-2 possible for each of the other two types.
v(2) = 36:
27 ways to have 4,0-2,0-2;
& 9 ways to have 3,3,0-2.
Kemudian pion 8-k lainnya mungkin masih Ps, atau berubah menjadi Qs, atau ditangkap.
Misalkan q adalah jumlah promosi ratu yang terlihat (yaitu ratu melebihi pelengkap asli 1).
Misalkan u_k (q) adalah banyaknya cara kombinatorial yang berbeda kita dapat mencapai ini (dalam hal bidak yang bertahan, ratu dan bidak yang ditangkap)
u_k(0) = 2*(9-k)
because we can have 0 to 8-k pawns, and the rest are captured,
independently we have 0 or 1 queen.
For q>0, u_k(q) = (9-k-q)
s(k) = sum(q=0,...,8-k) [u_k(q)]
= 2*(9-k) + (8-k) + (7-k) + ... 1
= (9-k)(12-k)/2.
Check:
s(8) = 2: 0-1Q
s(7) = 5: 0P,0-2Q; 1P;0-1Q
...
s(0) = 54: = 55-1
So the total number of of legal White collections is:
sum(k=0...8) [s(k)*v(k)]
= 8,694
Semua koleksi putih ini memang dapat dicapai, misalnya jika Hitam hanya memiliki raja kosong yang tersisa, tetapi dalam banyak situasi lain juga: ketidaksetaraan penawaran / permintaan tidak terlalu menuntut.
Latihan selanjutnya melibatkan penghitungan untuk setiap kombinasi N_w, M_w, A_w berapa banyak koleksi Putih yang ada.
Saya menghitung tabel jumlah koleksi berikut, diurutkan menurut jumlah total potongan di papan, seperti yang ditunjukkan pada tabel ini:
Untuk setiap jumlah unit dari 2-32, ini menunjukkan
- v_0: jumlah kandidat dasar tanpa mengkhawatirkan supply-demand,
- v_1: jumlah yang gagal tunggal terhadap permintaan-penawaran,
- v_2: jumlah yang gagal ganda terhadap permintaan-penawaran.
Untuk menghindari penghitungan ganda, jumlah posisi hukum dihitung sebagai v_1 - 2 * v_2 + v_3. Perhitungan saya sama persis dengan hasil Kryukov sebelumnya .
Perhatikan bahwa tidak ada kegagalan hingga mencapai 25 unit. Itu karena dengan 8 jepretan, semua koleksi promosi kandidat bisa tercapai.
Pertanyaan terbuka "kredit ekstra" (sedang dalam proses)
Penggemar retro lebih jauh membedakan antara warna kotak tempat para uskup berada, karena itu adalah invarian. Ini memiliki dampak besar yang terlihat pada legalitas potensial, merupakan bagian dari klasifikasi esensial untuk papan catur, dan juga merupakan perhatian estetika dalam komposisi. Istilah terkait kemudian adalah "perwira non-standar" (ratu atau uskup "berwarna" di luar yang pertama; benteng atau ksatria di luar yang kedua). Jumlah petugas yang hilang didasarkan pada 5 jenis yang sama. Penentuan tambahan ketidaksetaraan yang diperlukan dan cukup untuk mencirikan koleksi legal sekarang jauh lebih rumit.
Pendekatan terbaik mungkin pertama-tama menerapkan ketidaksetaraan penawaran / permintaan yang disesuaikan. Lalu dapatkah bertanya berapa banyak pion tambahan yang dibutuhkan untuk "mendorong" uskup tertentu ke warna yang benar?
Penangkapan bidak perwira / bidak akan menghasilkan 2/3 bidak yang masing-masing dipromosikan dalam kotak warna yang sama, tetapi tampaknya untuk setiap kelompok tersebut, kami bebas memilih warna secara mandiri.