טטרומינו
טטרומינו היא צורה גאומטרית המורכבת מארבעה ריבועים, כאשר כל אחד מהריבועים נמצא בניצב ללפחות ריבוע אחד אחר. הטטרומינו הן מקרה פרטים של הפוליאומינו בדומה לצורת דומינו או טרומינו (פוליאמינו בן 3 ריבועים, בקו אחד או בצורת L). מהיותה מורכבת מריבועים דו-ממדיים, כל צורה של טטרומינו היא דו-ממדית, זאת בניגוד לפולי-קובייה היכולה להיות מורכבת ממספר קוביות ועל כן מתקיימת גם במימד השלישי.
דוגמה מפורסמת מאוד של הטטרומינו היא משחק הטטריס שם הצורות מכונות לעיתים "טטרימינו". המילה טטרומינו נגזרת מיוונית מהתחילית טטרה (ארבע) ומן המילה דומינו[1].
משפחת הטטרומינואים[עריכת קוד מקור | עריכה]
טטרומינואים חופשיים[עריכת קוד מקור | עריכה]
כאמור, כל ריבוע של טטרומינו חולק צלע (או נמצא במקביל) לריבוע אחר לפחות. צורות אלה, הצורות המופיעות במשחק הטטריס, הן טטרומינואים חופשיים. לו הריבועים היו מתחברים זה לזה בקודקודיהם הצורה המתקבלת הייתה טטרומינו לא-חופשי. במילים אחרות, טטרומינו חופשי היא צורה אחידה שאינה מכילים חורים או מקטעים כלשהם. הטטרומינואים החופשיים הן מקרה פרטי של הפוליאומינואים החופשיים, שכן כל קבוצה של ריבועים ניתן לסדר כך שתיווצר צורה רציפה או צורה בעלת מרווחים או מקטעים.
טטרומינואים חד-צדדיים[עריכת קוד מקור | עריכה]
טטרומינואים חד-צדדיים הן טטרומינואים שניתן לקבל אותם כתוצאה מטרנסלציה ומרוטציה מתמטית אך לא משיקוף. ישנם שבעה סוגים של טטרומינואים חד צדדיים, מתוכם לשלושה יש סימטריה שיקופית, כך שאין זה משנה אם הם מוגדרים כטטרומינואים חופשיים או חד צדדיים. השלושה המיוחדת הזו היא[2]:
I (הטטרומינו הישר) ארבעה ריבועים ברצף על קו אחד.
O (הטטרומינו המרובע) ארבעה ריבועים המרכיבים ריבועים של 2 על 2.
T (טטרומינו T) שלושה ריבועים בקו כאשר מעל הריבוע האמצעי מוצב ריבוע נוסף.
שאר הטטרומינואים הם כיראליים והם[3]:
J: קו של שלושה ריבועים כאשר ריבוע מוצב מתחת לריבוע הימני ביותר בקו.
L: קו של שלושה ריבועים כאשר ריבוע מוצב מעל לריבוע הימני ביותר בקו.
S: שני ריבועים בקו הנמצאים מעל זוג ריבועים אחר ומוסטים ימינה.
Z: שני ריבועים בקו הנמצאים מעל זוג ריבועים אחר ומוסטים שמאלה.
כטטרומינואים חופשיים J שקול ל-L וההטרומינו S שקול לטטרומינו Z. אך בשני ממדים וללא שיקוף לא ניתן להפוך את J ל-L או את S ל-Z.
בעיות ריצוף הנוגעות לטטרומינואים[עריכת קוד מקור | עריכה]
למרות שהטטרומינואים החופשיים מורכבים מסך של 20 ריבועים, הם לא יכולים להתלכד לצורה מלבנית, בדומה להקסאומינואים, בעוד שסט של פנטומינואים (צורה המורכבת מ-5 ריבועים) יכולים להתלכד כך שימלאו מלבן ללא רווחים בארבע דרכים שונות. ההסבר לכך מתבסס על משפט גומורי[4].
מלבן המכיל עשרים משבצות וצבוע בתבנית של לוח שחמט מכיל עשרה ריבועים שחורים ועשרה ריבועים לבנים. אבל סט שלם של טטרומינואים חופשיים מורכב מ-11 ריבועים בצבע לבן ועוד 9 ריבועים בצבע שחור (הטטרומינו מסוג T יכול להיות מורכב מ-3 ריבועים מצבע אחד ועוד ריבוע אחד בלבד מצבע שני). אותו הדבר לגבי טטרומינואים חד-צדדיים: סט שלם מורכב מ-28 ריבועים כאשר יש 15 צבעים מצבע לבן (או שחור) ועוד 13 ריבועים מבצע שחור (או לבן). מאחר שכמות הריבועים מכל צבע אינה זוגית ואינה שווה הצורות המרכיבות את הטטרומינואים לא יכולות להתלכד למבנה מלבני[5].
מנגד, קבוצה ובה 2 מופעים מכל טטרומינו הכוללת יחד 40 ריבועים, יכולה להתלכד למלבן בגודל 4X10 או 5X8.
ישנם דרכים רבות בהן ניתן לצרף את המלבנים במלואים בעזרת צורות טטרומינו, אולם לכל בעיית ריצוף יש ייחודיות משלה:
- מלבן בגדול 5 על 8 יכול להיות מרוצף ב-99,392 דרכים שונות על ידי שימוש בזוגות של טטרומינואים (זוג מכל סוג). אם מתעלמים מפתרונות סימטריים או מפתרונות דומים (החלפת מיקום של זוגות) מתקבלים 783 פתרונות ייחודיים.
- מלבן בגודל 4 על 10 יכול להיות מרוצף ב-57,472 דרכים שונות. אם מתעלמים ממקרים בהם זוגות מחליפים מקום ומפתרונות זהים סימטרית, מתקבלים 449 פתרונות ייחודיים.
