مسألة رقعة الشطرنج المنقوصة

abcdefgh
8
h8 black cross
a1 black cross
8
77
66
55
44
33
22
11
abcdefgh
أحجية رقعة الشطرنج المشوهة.

مسألة رقعة الشطرنج المنقوصة من النوع الذي يطلب فيه تغطية رقعة شطرنج. طرح الأحجية جامو وسترن (بالإنجليزية: Gamow & Stern)‏ سنة 1958 وناقشها مارتن جاردنر في عمود ألعاب من الرياضيات بمجلة ساينتفك أمريكان (بالإنجليزية: Scientific American)‏. تنص الأحجية على ما يلي :على رقعة شطرنج 8×8 ينقصها مربعين متناظرين على القطر (ما يترك 62 مربع)،يطلب هل من الممكن تغطية الرقعة بقطع دومينو 2×1 عددها 31 تغطية كاملة ؟

الحل

[عدل]

لا يوجد حل للأحجية وتغطية الرقعة مستحيلة. مهما كانت طريقة توزيع قطع الدومينو على الرقعة، فإن أي قطعة دومينو تغطي مربعين بلونين مختلفين. ولما كانت الرقعة ينقصها مربعين من نفس اللون هذا ما يبقي مربعين آخرين من نفس اللون لا يمكن تغطيتهما بأي حال من الأحوال. على سبيل المثال، إذا احتفظ بالركنين الأبيضين، فإنه يتبقى 30 مربعا أبيض و32 مربعا أسود التي ستشملها أحجار الدومينو. يمكن وضع ما مجموعه 30 حجر دومينو على رقعة الشطرنج فيغطى 30 مربعا أبيض و30 مربعا أسود، تاركا مربعين سوداوين مكشوفين وقطعة دومينو غير مستعملة. والأمر نفسه (مع التغيير في الألوان) إذا اختير الاحتفاظ بالركنين الأسودين.[1]

نظرية جوموري

[عدل]

نفس الاستحالة بتغطية رقعة الشطرنج بحجب مربعين أبيضين. في حين أنه بحجب مربعين بلونين مختلفين، فإنه من الممكن تغطية الرقعة بالدومينو وهي النتيجة المعروفة بنظرية جوموري (بالإنجليزية: Gomory's theorem)‏،[2] نسبة للرياضياتي رالف جوموري Ralph E. Gomory الذي نشر الإثبات سنة 1973.[3] هذه النظرية يمكن إثباتها باستعمال مسار هاملتونياني لـمخطط بياني شبكي (بالإنجليزية: grid graph)‏ مكون من مربعات الرقعة. حجب مربعين من لونين مختلفين يقسم المسار إلى مسارين بعدد فردي من المربعات.

هوامش

[عدل]
  1. ^ McCarthy، John (1999)، "Creative Solutions to Problems"، AISB Workshop on Artificial Intelligence and Creativity، مؤرشف من الأصل في 2019-04-05، اطلع عليه بتاريخ 2007-04-27
  2. ^ Watkins، John J. (2004)، Across the board: the mathematics of chessboard problems، Princeton University Press، ص. 12–14، ISBN:9780691115030.
  3. ^ According to Mendelsohn, the original publication is in Honsberger's book. Mendelsohn، N. S. (2004)، "Tiling with dominoes"، The College Mathematics Journal، Mathematical Association of America، ج. 35، ص. 115–120، DOI:10.2307/4146865، JSTOR:4146865; Honsberger، R. (1973)، Mathematical Gems I، Mathematical Association of America.

مراجع

[عدل]

وصلات خارجية

[عدل]