פתיחת התפריט הראשי

ריבוע לטיני

בקומבינטוריקה, ריבוע לטיני הוא ריבוע של n שורות ו-n עמודות, שבכל שורה ובכל עמודה שלו כתובים אותם n סמלים שונים, בלי חזרות.

לדוגמה:

הדוגמה הקלה ביותר היא ריבוע שבשורה ה- i ובעמודה ה-j שלו כתוב i+j-1 או i+j-1-n (בוחרים בכל מקרה את המספר שנמצא בין 1 ל- n). באופן כללי יותר, לוח הכפל של כל חבורה הוא ריבוע לטיני. בסטטיסטיקה ריבועים לטיניים משמשים בתכנון ניסויים של שני משתנים. מקורו של המונח 'ריבוע לטיני' הוא בכך שלאונרד אוילר שחקר אותם השתמש באותיות לטיניות כסמלים.

פעולות על ריבועים לטינייםעריכה

ריבועים שקוליםעריכה

אם מסדרים מחדש את השורות או את העמודות של ריבוע לטיני, או מחליפים את הסימנים זה בזה, מתקבל ריבוע לטיני חדש. זוהי דוגמה לפעולה של החבורה   (כאשר   היא החבורה הסימטרית) על קבוצת הריבועים הלטיניים. לריבועים המתקבלים מריבוע נתון על ידי פעולות אלה קוראים ריבועים שקולים (Isotopic squares). מכיוון שריבועים שקולים שייכים לאותו מסלול תחת הפעולה של  , השקילות היא אכן יחס שקילות. כשסופרים ריבועים לטיניים מגודל מסוים, נוח לספור את מחלקות השקילות במקום את הריבועים הבודדים.

ריבועים צמודיםעריכה

נסמן ב-   את הערך המופיע בשורה ה-i והעמודה ה-j של הריבוע A. את התנאי על הופעת כל ערך פעם אחת בכל שורה ובכל עמודה אפשר לנסח מחדש כך: ב-  השלשות  , כל שני רכיבים עוברים על כל   האפשרויות. מכאן רואים שהתפקידים של "שורה", "עמודה" ו"ערך" בתיאור של ריבוע לטיני הם סימטריים. אפשר להחליף אותם, ולקבל ריבוע חדש. זוהי למעשה פעולה נוספת, של החבורה  . ששת הריבועים המתקבלים באופן זה מריבוע נתון הם צמודים (conjugate) זה לזה.

ריבועים דומיםעריכה

כשמשלבים את השקילות והצמידות, כלומר את פעולת הערבוב של שורות, עמודות או סמלים עם פעולת ההחלפה בין שורות, עמודות וסמלים, צריך להבחין שהפעולות אינן מתחלפות: החלפת שתי שורות שלאחריה מחליפים בין תפקידי השורות והעמודות אינה זהה להחלפת התפקידים שאחריה מחליפים שתי שורות. במלים אחרות, החבורה של פעולות על ריבועים לטיניים הנוצרת מן הפעולות של   ושל   שהוזכרו קודם לכן, אינה המכפלה הישרה של שתי החבורות; זוהי דוגמה נאה למכפלת זר (wreath product), שהיא סוג מיוחד של מכפלה ישרה למחצה.

אם אפשר לעבור מריבוע אחד לריבוע אחר על ידי פעולת השקילות ואחריה פעולת הדמיון (או להפך, הסדר אינו חשוב), אז שני הריבועים הם ריבועים דומים. גם יחס זה הוא יחס שקילות, והמחלקות קרויות 'מינים'. כל מין של ריבועים לטיניים כולל לכל היותר שש מחלקות-שקילות.

מספרם של הריבועים הלטינייםעריכה

לא ידועה נוסחה הקובעת את מספרם של הריבועים הלטיניים בגודל n; גם נוסחאות למספרן של מחלקות השקילות או של המינים, אינן ידועות. להלן מספר הריבועים בגודל n שהם 'ממוינים', כלומר שהשורה הראשונה והעמודה הראשונה ממוינות בסדר עולה (כדי לקבל את מספר הריבועים הלטיניים הכולל, יש להכפיל ב-  ).

מספר הריבועים הלטיניים בגודל נתון
n מספר הריבועים הממוינים
1 1
2 1
3 1
4 4
5 56
6 9408
7 16942080
8 535281401856
9 377597570964258816
10 7580721483160132811489280
11 5363937773277371298119673540771840

להלן מספרן של מחלקות השקילות ושל המינים. מספר הריבועים במחלקת שקילות מחלק את  , ומספר מחלקות השקילות בכל מין מחלק את 6.

מחלקות שקילות ומינים של ריבועים לטיניים
n מינים מחלקות שקילות
1 1 1
2 1 1
3 1 1
4 2 2
5 2 2
6 12 22
7 147 564
8 283657 1676267
9 19270853541 115618721533
10 34817397894749939 208904371354363006

השלמה לריבוע לטיניעריכה

אחת הבעיות המעניינות הקשורות לריבועים לטיניים היא זו של השלמת מידע חלקי: נתונים חלק מהערכים בריבוע בגודל n-על-n, ומעוניינים להשלים את כל האחרים כך שיתקבל ריבוע לטיני. הדבר בלתי אפשרי אם הערכים הנתונים כבר כוללים חזרות (בשורות או בעמודות), אך גם אם אין בנתונים חזרות, זה עדיין לא מבטיח שההשלמה אפשרית.

לעומת זאת, אם נתונות רק מספר שורות שלמות (ללא חזרות בשורות או בעמודות), אז תמיד אפשר להשלים אותן לריבוע לטיני - זוהי תוצאה ממשפט החתונה של Hall.

טיפוסים והכללותעריכה

ריבועים סימטרייםעריכה

יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים סימטריים ( ) שהאלכסון שלהם קבוע, לבין פירוקים של הגרף השלם על n קודקודים ל-איחוד של n-1 התאמות מלאות (פירוק כזה נקרא 1-factorization).

יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים עם סימטריה מלאה (סימטריים כנ"ל, וכן   אם ורק אם  ), שהאלכסון שלהם הוא הזהות ( ), לבין מערכות שטיינר משולשות.

ריבועים מאונכיםעריכה

שני ריבועים לטיניים A ו- B הם ריבועים מאונכים (או אורתוגונליים) אם כאשר כותבים אותם יחד באותו ריבוע,   הזוגות   שונים זה מזה. במלים אחרות, בכל זוג רכיבים ברביעיות   מופיעות כל   האפשרויות.

בסביבות 1780 מצא לאונרד אוילר דרך לבנות זוגות של ריבועים לטיניים בכל גודל שאינו מהצורה 4m+2. מאחר שאין זוג של ריבועים לטיניים מאונכים בגודל 2, שיער אוילר שלא קיימים ריבועים מאונכים בגדלים 6, 10, 14 וכו'. ההשערה קיבלה חיזוק כאשר ב-1901 הוכיח האיטלקי גסטון טרי (Gaston Tarry) באמצעות כוח גס שלא קיים זוג ריבועים מאונכים בגודל 6. ואולם, בשנת 1959 מצאו פארקר, בוסה ושריקאנדה (E. T. Parker‏, Raj Chandra Bose‏, Sharadchandra Shankar Shrikhande) זוג ריבועים מאונכים בגודל 10, והראו שקיים זוג כזה בכל גודל (פרט ל-2 ול-6).

בעיה שעדיין נותרה פתוחה, היא מציאת המספר המקסימלי של ריבועים לטיניים בגודל n, המאונכים בזוגות. ידוע כי מספר זה לא יכול לעלות על  , וכי הוא שווה בדיוק למספר זה, כאשר n מספר ראשוני או חזקה של מספר ראשוני. שאלה זו קשורה גם לגאומטריה פרויקטיבית סופית: קיים מישור פרויקטיבי סופי מסדר n, אם ורק אם קיימים   ריבועים לטיניים בגודל n המאונכים בזוגות.

הרחבות למימד גבוהעריכה

היפרקוביה לטינית היא ההכללה של הריבוע הלטיני ל-n ממדים ומשמשת לתכנון ניסויים בממדים גבוהים יותר.

דוגמאותעריכה

להלן דוגמאות לכל המינים של ריבועים לטיניים, עד גודל 5.

 


 


 

ריבועים לטיניים וחידות מתמטיותעריכה

המשחק סודוקו מבוסס על ריבוע לטיני בגודל 9, עם דרישות נוספות על המספרים בתשעה תת-ריבועים בגודל 3.


קישורים חיצונייםעריכה

  מדיה וקבצים בנושא ריבוע לטיני בוויקישיתוף