Buzilgan shaxmat taxtasi muammosi - Mutilated chessboard problem

Shaxmat taxtasi480.svg
a8 qora xoch
h1 qora xoch
Buzilgan shaxmat taxtasi muammosi

The buzilgan shaxmat taxtasi muammosi a plitka jumboq faylasuf tomonidan taklif qilingan Maks Blek uning kitobida Tanqidiy fikrlash (1946). Keyinchalik u tomonidan muhokama qilindi Sulaymon V. Golomb (1954), Gamov va Stern (1958) va tomonidan Martin Gardner uning ichida Ilmiy Amerika ustun "Matematik o'yinlar "Muammo quyidagicha:

Standart 8 × 8 deylik shaxmat taxtasi 62 ta kvadrat qoldirib, ikkita diagonal qarama-qarshi burchakka ega. 31 ni joylashtirish mumkinmi? domino bu kvadratlarning barchasini qoplash uchun 2 × 1 o'lchamda?

Adabiyotda ushbu muammoning aksariyat fikrlari dalilsiz "kontseptual ma'noda" echimlar beradi.[1] Jon Makkarti uchun qiyin muammo sifatida taklif qildi avtomatlashtirilgan dalil tizimlar.[2] Aslida, uning yordamida qaror xulosa chiqarish tizimi juda qiyin.[3]

Qaror

Buzilgan shaxmat taxtasi muammosi misoli.
Shaxmat taxtasining rangli bo'sh kvadratlarga o'xshash misoli (o'rtada ikkita bo'sh qora kvadratga e'tibor bering)

Jumboqni bajarish imkonsiz. Shaxmat taxtasiga qo'yilgan domino har doim bitta oq kvadrat va bitta qora kvadratni qoplaydi. Shuning uchun doskaga joylashtirilgan domino to'plami har bir rangning teng miqdordagi kvadratlarini qamrab oladi. Agar ikkita oq burchak taxtadan olib tashlangan bo'lsa, unda 30 ta oq kvadrat va 32 ta qora kvadrat domino bilan qoplanadi, shuning uchun bu mumkin emas. Agar buning o'rniga ikkita qora burchak olib tashlansa, unda 32 ta oq kvadrat va 30 ta qora kvadrat qoladi, shuning uchun yana mumkin emas.[4]

Analog

Shunga o'xshash muammo, o'zgarmas shaxmat taxtasining burchak maydonidan boshlangan chumolining har bir maydonga bir marotaba tashrif buyurib, qarama-qarshi burchak maydonida tugatishi mumkinligini so'raydi. Diagonal harakatlarga yo'l qo'yilmaydi; har bir harakat daraja yoki fayl bo'ylab bo'lishi kerak.

Xuddi shu mulohazadan foydalanib, bu vazifani bajarish mumkin emas. Masalan, agar boshlang'ich kvadrat oq bo'lsa, chunki har bir harakat oq va qora kvadratlar orasida o'zgarib tursa, har qanday to'liq turning yakuniy kvadrati qora rangda bo'ladi. Biroq, qarama-qarshi burchakli kvadrat oq rangga ega.[5]

Gomori teoremasi

a8b8c8d8e8f8g8h8
a7b7c7d7e7f7g7h7
a6b6c6d6e6f6g6h6
a5b5c5d5e5f5g5h5
a4b4c4d4e4f4g4h4
a3b3c3d3e3f3g3h3
a2b2c2d2e2f2g2h2
a1b1c1d1e1f1g1h1
A
a8b8c8d8e8f8g8h8
a7b7c7d7e7f7g7h7
a6b6c6d6e6f6g6h6
a5b5c5d5e5f5g5h5
a4b4c4d4e4f4g4h4
a3b3c3d3e3f3g3h3
a2b2c2d2e2f2g2h2
a1b1c1d1e1f1g1h1
B
Ushbu Gamilton tsiklida bitta qora va bitta oq kvadratni olib tashlash (x bilan ko'rsatilgan misollar) bitta (A) yoki ikkita (B) yo'llarni juft sonli kvadratlarga olib keladi

Xuddi shu imkonsiz dalil shuni ko'rsatadiki, yo'q domino plitka har qanday ikkita oq kvadrat shaxmat taxtasidan chiqarilganda mavjud bo'ladi. Biroq, qarama-qarshi ranglarning ikkita kvadratchasi olib tashlangan bo'lsa, unda qolgan taxtani har doim domino bilan plitka qilish mumkin; bu natija deyiladi Gomori teoremasi,[6] va matematik nomi bilan atalgan Ralf E. Gomori, uning dalili 1973 yilda nashr etilgan.[7] Gomory teoremasini a yordamida isbotlash mumkin Gamilton tsikli ning panjara grafigi shaxmat taxtasi kvadratlari tomonidan shakllangan; ikkita qarama-qarshi rangdagi kvadratlarning olib tashlanishi bu tsiklni ikkita yo'lga bo'linadi, ularning har biri juft kvadratchalar bilan, ikkalasini ham dominolarga bo'lish oson.

Shuningdek qarang

Izohlar

  1. ^ Endryus, Piter B.; Bishop, Metyu (1996), "To'plamlar, turlar, belgilangan nuqtalar va shaxmat taxtalari to'g'risida", Analitik jadvallar va shunga o'xshash usullar bilan isbotlangan teorema: 5-Xalqaro seminar, Tableaux '96, Terrasini, Palermo, Italiya, 15-17, 1996, Ishlar, Kompyuter fanidan ma'ruza matnlari, Springer-Verlag, adabiyotdagi muammoni davolashning aksariyati uni kontseptual ma'noda hal qiladi, ammo aslida Makkartining asl formulalarining ikkalasida ham teoremani isbotlamaydi.
  2. ^ Arthan, R. D. (2005), Z-da buzilgan shaxmat taxtasi teoremasi (PDF), olingan 2007-05-06, Buzilgan shaxmat teoremasi 40 yil oldin Jon Makkarti tomonidan avtomatlashtirilgan fikrlash uchun "yorilish uchun qattiq yong'oq" sifatida taklif qilingan.
  3. ^ Alexnovich, Maykl (2004), "Shaxmat taxtasi muammosini hal qilish juda qiyin", Nazariy kompyuter fanlari, 310 (1–3): 513–525, doi:10.1016 / S0304-3975 (03) 00395-5.
  4. ^ Makkarti, Jon (1999), "Muammolarning ijodiy echimlari", Sun'iy intellekt va ijodkorlik bo'yicha AISB seminari, olingan 2007-04-27
  5. ^ Miodrag Petkovich, Matematika va shaxmat: 110 ko'ngilochar muammolar va echimlar, ISBN  0-486-29432-3
  6. ^ Uotkins, Jon J. (2004), Taxta bo'ylab: shaxmat taxtasi matematikasi, Prinston universiteti matbuoti, bet.12–14, ISBN  978-0-691-11503-0.
  7. ^ Mendelsohnning so'zlariga ko'ra, asl nashr Xonsbergerning kitobida. Mendelsohn, N. S. (2004), "Domino bilan kafel", Kollej matematikasi jurnali, Amerika matematik assotsiatsiyasi, 35 (2): 115–120, doi:10.2307/4146865, JSTOR  4146865; Xonsberger, R. (1973), Matematik toshlar I, Amerika matematik assotsiatsiyasi.

Adabiyotlar

Tashqi havolalar