يمكن تبليط مربع طول ضلعه قوة للعدد 2، بعد حذف أي خلية واحدة، بقطع ترومينو على شكل L. [1] سنبني رقعة محددة ونراجع إحداثياتها، بدل الاكتفاء بصورة تبدو ممتلئة.
الخلاصة السريعة
- رقعتنا 8×8، والخلية المستبعدة (1,6)، عند ترقيم الأعمدة والصفوف من صفر.
- تبقى 63 خلية، فتحتاج التغطية إلى 21 قطعة، كل واحدة ثلاث خلايا.
- القطعة الأولى تغطي (3,3)، و(4,3)، و(4,4)، وتترك الركن المركزي للرُّبع المحتوي الخلية المحذوفة.
- بعدها نعالج أربعة مربعات 4×4؛ في كل واحد خلية غير متاحة بالضبط.
- فحصنا جميع مواضع الحذف في الأضلاع 1 و2 و4 و8 و16، أي 341 رقعة.
حدد شكل القطعة ومعنى الحذف
القطعة التي نستعملها تشغل ثلاث خلايا من مربع 2×2، مع ترك إحدى زواياه. يمكن تدويرها، لكن لا نسمح بتحويلها إلى ثلاثة مربعات في صف مستقيم. لا تتراكب قطعتان، ولا يمتد جزء منهما خارج الرقعة، وتبقى الخلية المحذوفة خالية في النهاية.
اجعل x رقم العمود من اليسار إلى اليمين، وy رقم الصف من الأسفل إلى الأعلى. تتراوح القيمتان من صفر إلى سبعة؛ إذن (1,6) في العمود الثاني والصف السابع عند العد المعتاد من واحد. طلاء هذه الخلية بالأسود في الرسم مجرد طريقة لتمييز المنع؛ لا نعدها قطعة إضافية.
حساب 64−1=63 ثم 63÷3=21 يخبرنا بعدد القطع اللازم إذا نجح التبليط. لكنه لا يعطينا مواضعها. لذلك نحتاج إلى قاعدة بناء ثم فحص مستقل لتغطية الخلايا؛ تساوي المساحة وحده لا يصلح صورة إثبات.
ضع أول قطعة حول مركز الرقعة
اقسم الرقعة بين العمودين 3 و4، وبين الصفين 3 و4. أصبحت لدينا أربعة مربعات طول ضلع كل منها 4. الحذف (1,6) يقع في الأعلى يسارًا. الخلايا الأربع الملاصقة للمركز هي (3,3)، (4,3)، (3,4)، (4,4).
نترك (3,4)، لأنها الركن المركزي للمربع الذي يحمل الحذف الأصلي. ونضع القطعة 1 في الثلاث الأخرى: (3,3)، (4,3)، (4,4). اختلاف x بين الحدين 1 واختلاف y كذلك 1، ولدينا ثلاث خلايا مختلفة من مربع 2×2، فتكون القطعة L صحيحة.
لم نحذف ثلاث خلايا جديدة من الرقعة. لقد غطيناها بالقطعة 1؛ تصبح غير متاحة للقطع التي سنضعها داخل المربعات الأصغر. التمييز مهم: الخلية الأصلية تبقى فارغة، أما الخلايا المركزية الثلاث فهي مشغولة فعلًا.
| المربع | الخلية | السبب |
|---|---|---|
| أسفل اليسار | (3,3) | القطعة 1 |
| أسفل اليمين | (4,3) | القطعة 1 |
| أعلى اليسار | (1,6) | الحذف الأصلي |
| أعلى اليمين | (4,4) | القطعة 1 |
كرر القرار داخل كل مربع صغير
نبدأ بأسفل اليسار. خليته غير المتاحة (3,3) تقع في ربعه الأعلى الأيمن. لذلك تغطي قطعته المركزية، رقم 2، الخلايا (1,1)، (2,1)، (1,2)، وتترك (2,2) لهذا الربع. ينتج أربعة مربعات 2×2، وفي كل واحد خلية فارغة أو مشغولة من قبل؛ تغطي قطعة واحدة الخلايا الثلاث المتبقية.
نستكمل هذا المربع قبل الانتقال إلى أسفل اليمين، ثم أعلى اليسار، ثم أعلى اليمين. لذلك أرقام القطع المركزية للمربعات الأربعة هي 2 و7 و12 و17. الأرقام تسجل ترتيب برنامجنا، ولا تعني أن بينها فرقًا في الحجم أو أن القاعدة تفرض هذه الأسماء.
في أعلى اليسار، حيث الحذف الأصلي، تغطي القطعة 12 الخلايا (1,5)، (2,5)، (2,6). لاحظ أنها لا تغطي (1,6). هذه مراجعة محلية مفيدة: تغيير موضع الخلية المستبعدة يجب أن يغيّر الزاوية التي نتركها في قرار التقسيم المناسب.
لماذا تستمر الفكرة إلى النهاية؟
أساس الاستقراء مربع 2×2 ناقص خلية، فتغطي الباقي قطعة واحدة. وعند مضاعفة الضلع نقسم إلى أربعة مربعات، ثم نضع قطعة مركزية في الثلاثة التي لا تحمل الحذف الأصلي. يصبح لكل مربع صغير موضع واحد مستبعد من العمل داخله، فنطبق فرض الاستقراء عليه. المربعات لا تتداخل، والقطعة المركزية تغطي المواضع الثلاثة المحجوزة لها. [2]
في المثال الحالي نرى النهاية صراحة: قطعة مركزية للرقعة، وأربع قطع مركزية في مربعات 4×4، وست عشرة قطعة لمربعات 2×2. المجموع 1+4+16=21. وفي التنفيذ سمحنا أيضًا برقعة 1×1 حذفت خليتها الوحيدة؛ تعيد قائمة قطع فارغة، وهي حالة توقف ملائمة للحساب.
إذا رمزنا لعدد القطع عند الضلع 2ⁿ بالرمز T(n)، فإن وصف البناء يعطينا T(0)=0 وT(n)=1+4T(n−1). التوسيع يعطي 1+4+…+4ⁿ⁻¹=(4ⁿ−1)/3. عند n=3 نحصل على 21، وعند n=4 نحصل على 85. النتيجة توافق حساب مساحة الخلايا المتاحة، لكنها هنا مرتبطة بخطة تغطية محددة.
افحص القطع دون الوثوق بطريقة توليدها
حفظ البرنامج كل قطعة كثلاثة أزواج إحداثيات. راجع الفاحص أنها ثلاثة مواضع مختلفة، وأن صندوقها المحيط 2×2، وأنها داخل الرقعة ولا تمس الخلية المستبعدة. ثم سجل عدد مرات تغطية كل خلية، ورفض أي تكرار، وقارن مجموعة الخلايا المغطاة بجميع خلايا الرقعة عدا الحذف.
فحصنا 341 رقعة تشمل كل موضع حذف في الأضلاع حتى 16. احتوت تلك النتائج 23188 قطعة. ومع فحوص المثال والمدخلات الخاطئة والتعداد الصغير، نجح 116773 تحققًا. وعمدنا إلى إفساد قوائم صحيحة بحذف قطعة، أو تكرارها، أو إدخال قطعة مستقيمة، أو نقل خلية خارج الحدود؛ رفضها الفاحص.
ولمربع 4×4، جربنا أيضًا بحثًا مستقلًا يسرد جميع القطع الممكنة داخل كل كتلة 2×2 ثم يختار تغطيات لا تتداخل. لكل واحد من مواضع الحذف الستة عشر وجد حلًا واحدًا يوافق البناء. هذا تعداد صغير فعلي؛ لم نمدد حكم وحدانية الحل إلى رقعتنا 8×8.
اعرف أين تتوقف النتيجة
القاعدة المعروضة تثبت حالة مربع ضلعه قوة للعدد 2 مع حذف واحد. إذا طلبت من برنامجنا ضلعًا 3 أو موضع حذف خارج الرقعة، فسيرفض المدخل. رفض البرنامج يعني أن المدخل خارج نطاقه المعلن؛ لا يحكم وحده على كل مسألة تبليط مختلفة.
ولرؤية الفرق بين المساحة وإمكان الوضع، خذ شريطًا من صف واحد وسبع خلايا واحذف طرفه. تبقى ست خلايا، وهو عدد يقبل القسمة على ثلاثة، لكن لا تتسع أي قطعة L داخل صف واحد. أكد تعداد المواضع أن هذه اللوحة لا تملك حلًا. لذا سجل شكل اللوحة والقطعة والحذف معًا، ثم افحص خلايا الحل واحدة واحدة.
المصادر
أُعد المقال والرسوم بمساعدة الذكاء الاصطناعي، مع تنفيذ الفحوص الحسابية المذكورة. لم تجر مراجعة بشرية مستقلة أو تجربة قص فعلية.