أحجية ترومينو من نورتون ستار

المصدر الأصلي للمقالة – https://nstarr.people.amherst.edu/trom/intro.html

حول الأحجية – النسخة المادية والنسخة الافتراضية

tromino puzzle

أحجيةv-21 الأساسية تتكوَّن من 21 قطعة على شكل مُربعات مثل النوع المعروض، وهي تتألف من ثلاثة مربعات وبلاطة مربعة إضافية ولوحة، 8 x 8 شبكة مربعة ذات مربعات لها نفس حجم مربعات البلاط. تحتل البلاطات ما مجموعه 3 x 21 + 1 = 63 + 1 = 64 مربعًا، وهو نفس عدد المربعات الموجودة في رقعة الداما. فيما يلي سوف نُسمي هذه قطع الزاوية بـ (الترومينو) وهو أبسط اسم مُستخدم لها وهناك عدّة اسماء أخرى تشمل (L-trominoes و L-triominoes و V-trominoes).

للعب النُسخة المادية من هذه الأحجية، فأنت تحتاج إلى 21 بلاطة ترومينو، وقطعة مربعة واحدة، وقاعدة تُشبه رُقعة الشطرنج 8 × 8 . قم أولاً بوضع القطعة المربعة المفردة في أي من المواقع الـ 64 المربعة على القاعدة. ثم املأ المربعات الـ 63 المتبقية بالترومينو حتى لا يكون هناك تداخل أو مربع غير مُعبأ. يسمى هذا الحل للغز ملء مربع 8 × 8 . بدلاً من ذلك، ابدأ بوضع الترومينات على التوالي على لوحة الشطرنج (كل مربع يشغل ثلاثة مربعات فقط من نمط الشبكة) وعندما يتم وضع الـ 21 قطعة، يُمكنك أن تضع القطعة الأخيرة في الموضع الوحيد المُتبقي.

إليك الخلفية التاريخية من النسخة التجارية من هذه الأحجية التي يتم تسويقها من قبل شركة Kadon Enterprises . ففي الاجتماع السنوي لجمعية الرياضيات الأمريكية خلال يناير 2000 ، تلقى آرثر بنيامين جائزة Haimo للتدريس المُتميز. وفي كلمته التي ألقاها أثناء حفل توزيع الجوائز أعطى دليلًا عن طريق الاستقراء؛ وأكَّد على أن هذا المنطق أن مربع خلية 2n x 2n (أي لوحة شطرنج تحتوي على مربعات 2n في كل جانب) ومع وجود خلية واحدة مشغولة تكون هناك خلية واحدة مشغولة ويُمكن دائمًا مُحاذاتها باستخدام الترومينات.

بعد ثلاث سنوات من سماع ملاحظات بنيامين كُنت ألقي محاضرة حول الاستقراء وتذكرت برهانه المُفضَّل. استكمالًا للأمثلة التي أعددتها سلفًا، قُمت بإعلان هذه الحجة الكلاسيكية بسبب سليمان غولومب مُعتقدًا بأن اللغز الفعلي سوف يُضيف عنصرًا من الواقع وقد يثير الاهتمام لطريقة الاستقراء وبالفعل أرسلت المُلاحظة إلى Kadon Enterprises وهي الشركة الرائدة في صناعة الأحجيات؛ وقد سألتهم إذا كان لديهم أي شيء يُمكنني شراؤه بهذه المواصفات ولم يكن لديهم، لذلك سألت عمّا إذا كان يُمكنهم تقديم أُحجية بها المواصفات التي طلبتها، وبالفعل أبدَّت رئيسة مؤسسة Kadon Enterprises اهتمامًا خاصًا بهذه الأحجية. وقد اقترحت استخدام عدة ألوان مختلفة لبلاط ترومينو، مما يجعل هذا اللغز يبدو أكثر إثارة للاهتمام مما كنت أتخيله في الأصل. لقد اخترت بلاطًا شفافًا وأكثر برودة من البلاط الغامق وغير الشفاف، واخترت الأزرق والأكوا والجمشت لقطع الترومينو.

سألت كيت عما إذا كنت تسمح لمؤسسة Kadon Enterprises بإضافة اللغز إلى مجموعة العناصر التي يبيعونها ووافقت فورًا وأرادت فقط البعض منها لاستخدامها الشخصي. وقد دُهشت حينما أخبرتني بأنني سوف أتلقى حصة من الأرباح! لم يكن هذا هدفي أبدًا وقد تبرعت بجميع حقوق الامتياز إلى كلية أمهيرست والجمعية الرياضية الأمريكية.

أخرج كادون اللغز تحت اسم “Vee-21″؛ راجع www.gamepuzzles.com/polycub2.htm#V21. وتأتي هذه النسخة التجارية، بثلاثة ألوان أكريليك شفافة مع كُتيب من أربعين صفحة يُقدم عددًا من التحسينات والتطويرات على اللغز الأساسي. وقد ساهمت كيت بإضافة بعض التطويرات على اللغز الأساسي، وبعض الألعاب الاستراتيجية التي يلعبها شخصان، كما أنها قد اقترحت فصل ألوان البلاط. كما اكتشفت الاحتمالات الجمالية في صناعة الأنماط المُتناظرة. كما أن كيت قد دعت أوريل ماكسيم لإضافة بعض من تحدياته التي تُشبه المتاهات للبلاط مع الترومينو، ويتضمن الكتيب مجموعة متنوعة من القوالب المستطيلة مع خطوط تم اختيارها بشكل استراتيجي من الشبكات المظلمة لتكون بمثابة حواجز لا يمكن وضع الترومينات عليها.

كما توجد نسخة من هذه الألغاز التفاعلية مُتاحة للعب على الكمبيوتر. فقد تم تطوير اللغز 8 × 8 من قبل اثنين من طلابي وقد ساهم واحد من زملائهم في تطوير لغز M-by-N الذي يُمكن الإستمتاع به على معظم أنظمة التشغيل وقد يكون بطيئًا بعض الشيء في التحميل ولكنه أكثر مرونة إلى حد ما من النُسخ الأخرى مما يسمح باختيار أي عدد من الصفوف والأعمدة بين 2 و 32. يحتوي لغز 8 × 8 (الذي يُمكن تشغيله على مُتصفح Internet Explorer على مُختلف أجهزة الكمبيوتر ونُظُم التشغيل) على خصائص مُختلفة للماوس وهو يقتصر على ثلاثة ألوان من الترومينو. ولكن يُمكن لعب كل الإصدارَيْنِ بإستخدام الماوس والكيبورد، وهما يتمتعان بجاذبية استثنائية رُغم أن الأحجية قد تم تطويرها قبل 4 أعوام فقط!

التاريخ

الدليل على أن أي عدد صحيح موجب سيكون n وأن مربع 2n x 2n مع خلية واحدة مشغولة يُعتبَّر مُربعًا منقوصًا ويمكن دائمًا تجنبه باستخدام الترومينو يرجع إلى المقال الذي نشره سليمان غولمب عام 1954 [9] في المجلة الأمريكية الرياضية الشهرية. كما هو مذكور أعلاه، كان لتوضيح أن حُجة غولومب للمربعات الناقصة 2n x 2n أن اللغز تم حبكه، وفي نفس المقالة تم تقديم وتعميم مُصطلح الترومينو ومشتقاته بوليومينو. والبوليومينو هو عبارة عن مجموعة مُتصلة من المربعات المُتطابقة التي لها خاصية أن أي مربعَيْنِ لا يلمسانها أو يلتقيان على طول حافة مشتركة كاملة. الشكلان الوحيدان لترومينو هما ثلاثة مربعات متتالية والشكل L لهذا اللغز، وهنا يشير “الترومينو” إلى الأخير فقط.

دليل غولومب هو مثال من الدرجة الأولى على الاستقراء الرياضي، وهو أبعد من ما يكون عن الأناقة المطلقة للحُجة وهو يقف على النقيض من الأمثلة والتمارين الموجودة في معالجات الكتب الاستقراء والتي تتكون عادة من صيغ متنوعة للمبالغ المحدودة وعدم المساواة وما شابه. كان أول ظهور لهذا الدليل في منشور عام كان في مجلة جوزيف ماداتشي للرياضيات الترفيهية (RMM)، حيث أدرجها غولومب في سلسلة مقالاته الأولى عن البوليومينو المنشورة في RMM [10].

وفي عام 1957 كان مارتن غاردنر يكتب عمودًا عمليًا بشكلٍ شهري وكان يقدم فيه polyominoes لجمهور أوسع، وقد أشار إلى مُلاحظة أن “اللوحة إذا كان بها مُربعًا مفقودًا فيُمكن ملئه بالقطعة رقم 21 في أي وقت” [6 ، ص. 154]. في كتابه الأول من أعمدة الألعاب الرياضية التي تم جمعها، أوضح جاردنر بملاحظة أن “حجة استقراء بارعة توضح أن قطعة الترومينو رقم 21 ومونومينو واحد سيغطي لوحة 8 × 8 بغض النظر عن مكان وضع المونومينو” [8 ، ص. 126].

ظهرت حجة مواضع الترومينو على المربعات الناقصة ونظرية 2n x 2n في سلسلة من الكتب ومقالات RMM. وقد تم شرحها في البوليومينو الكلاسيكية لغولومب [11 ، 1965 ، ص 21-22] وتُقدم الطبعة الثانية من هذا الكتاب [11 ، 1994 ، ص. 5] تاريخًا غنيًا ومسحًا شاملاً لهذا الموضوع المثير للاهتمام، وهي مليئة بالصور والألغاز.

فهي تحتوي على 22 صفحة من المراجع التي نُقلت عن الكتب والمقالات، ويسرد فهرس الأسماء 81 فردًا ويتم الإشارة إلى عدد غير قليل منهم أكثر من مرة في نص الكتاب. سيتم التعرف على العديد من هذه الأسماء من قبل هواة اللعبة وعلماء الرياضيات الهواة وكذلك من قبل المتخصصين في مجال الألعاب أو الرياضيات.

وهناك وصف للكتاب في المراجعة [17] لجورج مارتن. في عام 1976، قدم روس هونسبرغر تطبيقًا واضحًا ومُفصلاً لحجة غولومب إلى لوحة الداما في أحجاره الرياضية الثانية [13 ، ص. 61]. تم ذكر الفكرة الأساسية للدليل أيضًا في كتاب جورج إي مارتن المخصص لبلاط البوليومينو [16 ، ص 27-28]. إن مراجعة ديفيد سينجماستر [22] من هذا الكتاب الأخير مثيرة للاهتمام جدًا لأنها تُقدم نظرة جميلة للموضوع وتاريخه.

هذا الموضوع شائع بشكل متزايد في النصوص والكتب المُختلفة التي تتناول الرياضيات والألعاب. على سبيل المثال، يظهر في نصوص الرياضيات المنفصلة لسوزانا إب [5 ، ص. 234] وريتشارد جونسونباو (الذي يذكر وضع الترومينو على المستطيلات بأن مصدره هو تصميم تخطيط VLSI) [14 ، ص 58-59] ، وكينيث روزين [20 ، ص 247-8]. تمت مُعالجة مواضع ترومينو أيضًا في كتاب دانيال فيليمان حول بناء البراهين [26 ، ص 271-275] وكتب المشاكل التي كتبها جون ب. أنجيلو ودوغلاس ب. ويست [1 ، ص. 75] وبقلم جي هيرمان ، رادان كوسيرا جارومير ايم [12 ، ص. 271]. إن التوضيح الأكثر بلورة لحجة غولومب هو “دليل بدون كلمات” لروجر نيلسن ، الوارد في كتابه الثاني والذي يحمل نفس العنوان [19 ، ص. 123].

استفاد هذا المجال من الرياضيات الترفيهية من تدفق مستمر للتحقيق والمشاكل المقترحة. في عامي 1985 و 1986، درس I-Ping Chu و Richard Johnsonbaugh مسألة ملء المربعات الناقصة حيث لم تعد هناك حاجة إلى قوة 2 بشكل عام أو القطع الناقصة أو غير الناقصة [3 ، 4 ]. تضمن كتاب جورج مارتن فصلاً كاملًا مخصصًا لقطع الترومينو [16 ، ص 23-37].

يعالج Ilvars Mizniks مشاكل تلوين بلاط الترومينو وهو يعترف باختيار اللون Kadon Vee-21 كان مصدرًا إلهام http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf“>لبحثه! [18]. مقالة عام 2004 [2] بقلم جيه مارشال آش وسولومون غولومب، حول قطع الترومينو لمربعات ناقصة تحتوي على العديد من النتائج الجديدة والأساسية أحدها يجيب على سؤال قديم لـ Chu و Johnsonbaugh، وينتهي Ash و Golomb بمشكلة مفتوحة حول مستطيلات ناقصة 2 (مستطيلات مع إزالة خليتين).

يُعد الإنترنت مصدرًا جيدًا لعرض معلومات حول القطع ومواضعها. على سبيل المثال، فإن البحث عن “tromino” أو “tiling” سوف يعرض لك تطبيقات صغيرة مثل تلك التي كتبها ألكسندر بوجومولني على:
(http://www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml) والبحث الخاص بكريستوفر مواتا المنشور على (http://www.utc.edu/Faculty/Christopher-Mawata/trominos/) وتوضح هذه الأبحاث ألغاز الترومينو بعدة أحجام.

الاختلافات

فيما يلي بعض المصادر الإضافية حول لغز ترومينو التي قد يحتاج إليها القراء. الأول اقترحه أخي ريموند بيت، والذي سأل عن كيفية ترتيب الترومينو في شبكة 8 × 8 لزيادة عدد المربعات غير المشغولة. يمكننا توضيح ذلك: مسار واحد يفترض أن البلاط والشبكة فيلكرو بحيث تبقى في مكانها ، في حين يمكن للمرء بدلاً من ذلك أن يسمح للبلاط بالانزلاق بحيث يسمح بالضغط في أكبر عدد ممكن من البلاط (دائمًا داخل خطوط الشبكة). لم يكن بيت مدركًا أن إصدارvelcro هو اختلاف في لغز تحديد المواقع pentomino الخاص بـ Golomb كما وصفه Gardner [7 ، ص. 128] و [8 ، ص. 133]. طبق غولومب هذا اللغز على لعبة بنتومينو لشخصين [7 ، ص. 128] و [8 ، ص 133-135] كما أنه طبقها على لغز ترومينو أيضًا. أفاد ديفيد كلارنر عن لعبة بينتومينو لشخصين، بان كاي (التي طورها أليكس راندولف وأصدرتها دار النشر فيليبس في عام 1961) ، والتي تضمنت القيد التالي:

أهم قاعدة هي أنه يحظر وضع قطعة داخل منطقة مغلقة من اللوحة إذا كانت تحتوي على أقل من 5 مربعات ستبقى فارغة بعد ذلك، ما لم تملء هذه الخطوة المنطقة بالضبط. 8] (انظر [21 ، ص 75] لمزيد من المعلومات حول راندولف وبان كاي).

اتجاه آخر ثلاثي الأبعاد. ضع في اعتبارك مكعبًا بطول الضلع n2، يحتوي على 23n خلايا، إحداهما مشغولة. فهل يمكن تجانب الخلايا المتبقية مع ترومينو ثلاثي الأبعاد (ثلاثة مكعبات على شكل حرف L، واثنان منها يلتقيان الثالث في وجهان متجاوران لهذا الأخير)؟ الشرط الضروري (2n = 3k + 1) تبين أنه كافٍ أيضًا. [23 ، الفصل 6: بلاط ترومينو ثلاثي الأبعاد من Norton Starr] ، [24 ، الصفحات 72-87] ، و [25] تقدم حالة المكعب 4 x 4.4 بعض التحديات الصغيرة التي قد تثير اللاعبين الصغار.

المشاكل الأبسط توحي بسهولة وقد تم النظر فيها من قبل العديد من الآخرين. على سبيل المثال، هل يمكن استخدام المصفوفات المربعة بالكامل 3 x 3 و 6 x 6 مع الترومينو؟ هل يمكن تجانب كل مجموعة مربعة 5 x 5 7 x7؟ تعد هاتان اللغتان الأخيرتان أكثر تحديًا من الحالات الكاملة 33 x و x 66 و 8 x 8 الكاملة. بل أن هناك ما هو أبعد من ذلك، حيث يُمكن للقراء التفكير في إمالة المصفوفات المستطيلة المختلفة (انظر المراجع أدناه) فعند استخدام إصدار يحتوي على أكثر من لون واحد من الترومينو، مثل Kadon Vee-21 فكر في حواجز ذات ألوان مختلفة. على سبيل المثال، حاول ترتيب المربعات بحيث لا يُشارك اثنان من نفس اللون الحافة الواحدة. في الاتجاه المعاكس، حاول تجميع أكبر عدد ممكن من البلاط بلون واحد معًا قدر الإمكان. لكل من هذيْن النوعيْن من الأنماط، حاول أن تجعل البلاط يبدو متناظرًا حول قطر أو حول خط أفقي أو عمودي. فرص المتعة في هذا اللغز رائعة ومُتنوعة. ويمكن دراسة المستطيلات ذات الأحجام المختلفة من خلال النقر على لغز M-by-N. وإذا أردت تجربة نمط الألوان، فإن لغز Kadon سيكون هو الأفضل لك.

مراجع

J. P. D’Angelo and D. B. West, Mathematical Thinking: Problem-Solving and Proofs, Second edition, Prentice Hall, Upper Saddle River, NJ, 2000.

J. M. Ash and S. W. Golomb, “Tiling deficient rectangles with trominoes,” Math. Mag., 77 (2004), 46-55. (Available at math.depaul.edu/~mash/TileRec3b.pdf)

I. P. Chu and R. Johnsonbaugh, “Tiling deficient boards with trominoes,” Math. Mag., 59 (1986), 34-40.

I. P. Chu and R. Johnsonbaugh, “Tiling boards with trominoes,” J. Recreational Math., 18 (1985-86), 188-193.

S. S. Epp, Discrete Mathematics with Applications, Third edition, Thomson, Belmont, CA, 2004.

M. Gardner, “About the remarkable similarity between the Icosian Game and the Tower of Hanoi,” Scientific American, 196, (May, 1957), 150-156. This column was primarily devoted to Hamilton circuits, but ends with a section on checkerboard tiling problems: Gardner states that the February column’s checkerboard/domino problem “prompted Octave Levenspiel of Bucknell University to call my attention to a remarkable article by S. W. Golomb in American Mathematical Monthly for December, 1954.”

M. Gardner, “More about complex dominoes, plus the answers to last month’s puzzles,” Scientific American, 197, (December, 1957), 126-140. This Mathematical Games column starts by reporting the explosive impact of the May column’s brief account of Golomb’s work [6]: “In the year since this department was inaugurated, it has received more letters about one mathematical recreation than any other� the ‘pentomino’ problem� Hundreds of correspondents sent in widely varying solutions. Many testified to the problem’s strange fascination� .”

M. Gardner, The Scientific American Book of Mathematical Puzzles & Diversions, Simon and Schuster, New York, 1959. (Reprinted and updated as Hexaflexagons and Other Mathematical Diversions, University of Chicago Press, 1988.) [Chapter 13 of this first such collection combines the tiling material of [6] and [7] and is titled “Polyominoes.”]

S. W. Golomb, “Checker Boards and Polyominoes,” Amer. Math. Monthly, 61 (1954), 675-682.

S. W. Golomb, “The General Theory of Polyominoes Part I – Dominoes, Pentominoes and Checkerboards,” Recreational Math. Mag., Issue No. 4 (August, 1961), 3-12.

S. W. Golomb, Polyominoes, Scribner’s, New York, 1965. (Second edition: Polyominoes, Puzzles, Patterns, Problems, and Packings, Princeton University Press, Princeton, 1994.)

J. Herman, R. Kučera and J. �im�a, Counting and Configurations: Problems in Combinatorics, Arithmetic, and Geometry (Karl Dilcher, translator), Springer-Verlag, New York, 2003.

R. Honsberger, Mathematical Gems II, Mathematical Association of America, Washington, DC, 1976.

R. Johnsonbaugh, Discrete Mathematics, Sixth edition, Pearson Prentice Hall, Upper Saddle River, NJ, 2005.

D. Klarner, Box-Packing Puzzles. Multilithed notes, University of Waterloo, Ontario, 1973-74. 42 pages + title page. (Portions of this are summarized in Chapter 8 of Honsberger [13].)

G. E. Martin, Polyominoes, A Guide to Puzzles and Problems in Tiling, Mathematical Association of America, Washington, DC, 1991.

G. E. Martin, review of S. Golomb’s Polyominoes (1994 edition), Mathematical Reviews, MR1291821 (95k:00006), 1995.

I. Mizniks, “Computer Analysis of the 3 Color Problem for V-Shapes”, Acta Societatis Mathematicae Latviensis, Abstracts of the 5th Latvian Mathematical Conference, April 6-7, 2004, Daugavpils, Latvia. (Available at http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)

R. B. Nelsen, Proofs Without Words II, More Exercises in Visual Thinking, Mathematical Association of America, Washington, DC, 2000.

K. H. Rosen, Discrete Mathematics and Its Applications, Fifth edition, McGraw-Hill, New York, 2003. (To appear as Example 13, Section 4.1, in the sixth edition, 2007.)

J. N. Silva (Ed.) Recreational Mathematics Colloquium I (Conference Proceedings, Apr. 29-May 2, 2009. University of Évora), Associação Ludus, Lisboa, 2010.

D. Singmaster, review of G. E. Martin’s Polyominoes, Mathematical Reviews, MR1140005 (93d:00006), 1993.

A. Soifer, Geometric Etudes in Combinatorial Mathematics, Second Edition, Springer, New York, 2010.

N. Starr, �Tromino Tiling Deficient Cubes of Side Length 2n�, Geombinatorics XVIII(2) (2008), 72-87.

N. Starr, �Tromino Tiling Deficient Cubes of Any Side Length�, http://arxiv.org/abs/0806.0524 , June 3, 2008.

D. J. Velleman, How To Prove It: A Structured Approach, Second edition, Cambridge University Press, New York, 2006

مشاهدة المزيد