Parçalanmış satranç tahtası sorunu - Mutilated chessboard problem

Parçalanmış satranç tahtası sorunu

parçalanmış satranç tahtası sorunu bir döşeme bulmacası filozof tarafından önerilen Max Siyah kitabında Kritik düşünce (1946). Daha sonra tartışıldı Solomon W. Golomb (1954), Gamow ve Stern (1958) ve tarafından Martin Gardner onun içinde Bilimsel amerikalı sütun "Matematik Oyunları ". Sorun şu şekildedir:

Standart bir 8 × 8 varsayalım satranç tahtası çapraz olarak karşılıklı iki köşesi çıkarılmış ve 62 kare bırakılmıştır. 31 yerleştirmek mümkün mü domino tüm bu kareleri kaplayacak şekilde 2 × 1 boyutunda mı?

Bu problemin literatürdeki çoğu düşüncesi, ispatsız "kavramsal anlamda" çözümler sunar.^[1] John McCarthy bunu zor bir problem olarak önerdi otomatik kanıt sistemleri.^[2] Aslında, çözümü çözüm çıkarım sistemi katlanarak zordur.^[3]

Çözüm

Renkli boş kareler gibi görünen parçalanmış satranç tahtası örneği (ortadaki iki boş siyah kareye dikkat edin)

Bulmacayı tamamlamak imkansız. Satranç tahtasına yerleştirilen bir domino her zaman bir beyaz kareyi ve bir siyah kareyi kaplayacaktır. Bu nedenle, tahtaya yerleştirilen bir domino koleksiyonu, her rengin eşit sayıda karesini kaplayacaktır. İki beyaz köşe tahtadan kaldırılırsa, domino ile kapatılması gereken 30 beyaz kare ve 32 siyah kare kalır, bu yüzden bu imkansızdır. Bunun yerine iki siyah köşe kaldırılırsa, 32 beyaz kare ve 30 siyah kare kalır, yani yine imkansızdır.^[4]

Analog

Benzer bir problem, kullanılmamış bir satranç tahtasının köşe karesinden başlayan bir karıncanın her kareyi tam olarak bir kez ziyaret edip, karşı köşe karesinde bitirip bitiremeyeceğini sorar. Çapraz hareketlere izin verilmez; her hareket bir sıra veya sıra boyunca olmalıdır.

Aynı mantığı kullanarak bu görev imkansızdır. Örneğin, ilk kare beyazsa, her hareket siyah ve beyaz kareler arasında değiştiğinden, herhangi bir tam turun son karesi siyahtır. Ancak karşı köşedeki kare beyazdır.^[5]

Gomory teoremi

Bir

B

Bu Hamilton döngüsünde bir siyah ve bir beyaz karenin çıkarılması (× ile gösterilen örnekler), çift sayıda kareye sahip bir (A) veya iki (B) yol verir.

Aynı imkansızlık kanıtı, hayır domino döşeme satranç tahtasından herhangi iki beyaz kare kaldırıldığında vardır. Ancak, karşıt renkteki iki kare kaldırılırsa, kalan tahtayı domino ile döşemek her zaman mümkündür; bu sonuca denir Gomory teoremi,^[6] ve matematikçinin adını almıştır Ralph E. Gomory, 1973'te kanıtı yayınlanan.^[7] Gomory teoremi, bir Hamilton döngüsü of ızgara grafiği satranç tahtası karelerinin oluşturduğu; Karşıt renkli iki karenin kaldırılması, bu döngüyü, her ikisi de dominolara bölünmesi kolay olan, her biri çift sayıda kare olan iki yola böler.

Ayrıca bakınız

Notlar

^ Andrews, Peter B .; Bishop, Matthew (1996), "Setlerde, Tiplerde, Sabit Noktalarda ve Dama Tahtalarında", Analitik Tablolar ve İlgili Yöntemlerle Kanıtlayan Teorem: 5th International Workshop, Tableaux '96, Terrasini, Palermo, İtalya, 15-17th, 1996, Proceedings, Bilgisayar Bilimlerinde Ders Notları, Springer-Verlag, literatürdeki problemin çoğu incelemesi onu kavramsal anlamda çözer, ancak gerçekte McCarthy'nin orijinal formülasyonlarından herhangi birinde teoremin kanıtlarını sağlamaz.
^ Arthan, R.D. (2005), Z'de Parçalanmış Satranç Tahtası Teoremi (PDF), alındı 2007-05-06, Parçalanmış satranç tahtası teoremi, 40 yıl önce John McCarthy tarafından otomatik akıl yürütme için “kırılması zor bir ceviz” olarak önerilmişti.
^ Alekhnovich, Michael (2004), "Parçalanmış satranç tahtası probleminin çözümü katlanarak zor", Teorik Bilgisayar Bilimleri, 310 (1–3): 513–525, doi:10.1016 / S0304-3975 (03) 00395-5.
^ McCarthy, John (1999), "Sorunlara Yaratıcı Çözümler", Yapay Zeka ve Yaratıcılık Üzerine AISB Çalıştayı, alındı 2007-04-27
^ Miodrag Petkovic, Matematik ve Satranç: 110 Eğlenceli Problemler ve Çözümler, ISBN 0-486-29432-3
^ Watkins, John J. (2004), Tahtanın karşısında: satranç tahtası problemlerinin matematiği, Princeton University Press, s.12–14, ISBN 978-0-691-11503-0.
^ Mendelsohn'a göre, orijinal yayın Honsberger'in kitabında. Mendelsohn, N. S. (2004), "Domino ile Döşeme", Kolej Matematik Dergisi, Amerika Matematik Derneği, 35 (2): 115–120, doi:10.2307/4146865, JSTOR 4146865; Honsberger, R. (1973), Matematiksel Taşlar I, Amerika Matematik Derneği.

Referanslar

Gamow, George; Stern, Marvin (1958), Bulmaca-Matematik, Viking Basın ISBN 978-0-333-08637-7
Gardner, Martin (1994), En İyi Matematiksel ve Mantık Bulmacalarım, Dover, ISBN 0-486-28152-3

Dış bağlantılar

Jim Loy tarafından Kontrol Panosunda Domino
Dama Tahtası üzerinde Domino'lar
Gomory Teoremi Jay Warendorff tarafından, Wolfram Gösterileri Projesi.

[1] Andrews, Peter B .; Bishop, Matthew (1996), "Setlerde, Tiplerde, Sabit Noktalarda ve Dama Tahtalarında", Analitik Tablolar ve İlgili Yöntemlerle Kanıtlayan Teorem: 5th International Workshop, Tableaux '96, Terrasini, Palermo, İtalya, 15-17th, 1996, Proceedings, Bilgisayar Bilimlerinde Ders Notları, Springer-Verlag, literatürdeki problemin çoğu incelemesi onu kavramsal anlamda çözer, ancak gerçekte McCarthy'nin orijinal formülasyonlarından herhangi birinde teoremin kanıtlarını sağlamaz.

[2] Arthan, R.D. (2005), Z'de Parçalanmış Satranç Tahtası Teoremi (PDF), alındı 2007-05-06, Parçalanmış satranç tahtası teoremi, 40 yıl önce John McCarthy tarafından otomatik akıl yürütme için “kırılması zor bir ceviz” olarak önerilmişti.

[3] Alekhnovich, Michael (2004), "Parçalanmış satranç tahtası probleminin çözümü katlanarak zor", Teorik Bilgisayar Bilimleri, 310 (1–3): 513–525, doi:10.1016 / S0304-3975 (03) 00395-5.

[McCarthy-4] McCarthy, John (1999), "Sorunlara Yaratıcı Çözümler", Yapay Zeka ve Yaratıcılık Üzerine AISB Çalıştayı, alındı 2007-04-27

[5] Miodrag Petkovic, Matematik ve Satranç: 110 Eğlenceli Problemler ve Çözümler, ISBN 0-486-29432-3

[6] Watkins, John J. (2004), Tahtanın karşısında: satranç tahtası problemlerinin matematiği, Princeton University Press, s.12–14, ISBN 978-0-691-11503-0.

[7] Mendelsohn'a göre, orijinal yayın Honsberger'in kitabında. Mendelsohn, N. S. (2004), "Domino ile Döşeme", Kolej Matematik Dergisi, Amerika Matematik Derneği, 35 (2): 115–120, doi:10.2307/4146865, JSTOR 4146865; Honsberger, R. (1973), Matematiksel Taşlar I, Amerika Matematik Derneği.

[1]

[2]

[3]

[4]

[5]

[6]

[7]