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

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

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

نظرية جوموري 
نفس الاستحالة بتغطية رقعة الشطرنج بحجب مربعين أبيضين. في حين أنه بحجب مربعين بلونين مختلفين، فإنه من الممكن تغطية الرقعة بالدومينو وهي النتيجة المعروفة بنظرية جوموري ، نسبة للرياضياتي رالف جوموري Ralph E. Gomory الذي نشر الإثبات سنة 1973.
هذه النظرية يمكن إثباتها باستعمال مسار هاملتونياني لـمخطط بياني شبكي  مكون من مربعات الرقعة. حجب مربعين من لونين مختلفين يقسم المسار إلى مسارين بعدد فردي من المربعات.

هوامش

مراجع

وصلات خارجية 
  Dominoes on a Checker Board by Jim Loy
  Dominoes on a Checker Board
  Gomory's Theorem by Jay Warendorff, The Wolfram Demonstrations Project.

أحجيات منطقية
معضلات رياضيات متعلقة بالشطرنج