ריבוע לטיני

ריבוע לטיני
בקומבינטוריקה, ריבוע לטיני הוא ריבוע של (נאמר) n שורות ו- n עמודות, שבכל שורה ובכל עמודה שלו כתובים אותם n סמלים, בלי חזרות.
לדוגמא:
הדוגמא הקלה ביותר היא ריבוע שבשורה ה- i ובעמודה ה-j שלו כתוב i+j-1 או i+j-1-n (בוחרים בכל מקרה את המספר שנמצא בין 1 ל- n). באופן כללי יותר, לוח הכפל של כל חבורה (מבנה אלגברי) הוא ריבוע לטיני. בסטטיסטיקה ריבועים לטיניים משמשים בתכנון ניסויים. מקורו של המונח 'ריבוע לטיני' הוא בכך שלאונרד אוילר שחקר אותם השתמש באותיות לטיניות כסמלים.
תוכן עניינים<הסתר>
1 פעולות על ריבועים לטיניים
1.1 ריבועים שקולים
1.2 ריבועים צמודים
1.3 ריבועים דומים
2 מספרם של הריבועים הלטיניים
3 השלמה לריבוע לטיני
4 ריבועים מאונכים
5 דוגמאות
6 ריבועים לטיניים וחידות מתמטיות
//
<עריכה>
פעולות על ריבועים לטיניים
<עריכה>
ריבועים שקולים
אם מסדרים מחדש את השורות והעמודות של ריבוע לטיני, ומחליפים את הסימנים זה בזה, מתקבל ריבוע לטיני חדש. זוהי דוגמא לפעולה של החבורה (כאשר היא החבורה הסימטרית) על קבוצת הריבועים הלטיניים. לריבועים המתקבלים מריבוע נתון על-ידי פעולות אלה קוראים ריבועים שקולים (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.
<עריכה>
ריבועים מאונכים
שני ריבועים לטיניים A ו- B הם ריבועים מאונכים אם כאשר כיחד באותו ריבוע, הזוגות שונים זה מזה. במלים אחרות, כל זוג רכיבים ברביעיות עובר על כל האפשרויות.
בסביבות 1780 מצא לאונרד אוילר דרך לבנות זוגות של ריבועים לטיניים בכל גודל שאינו מהצורה 4m+2. מאחר שאין זוג של ריבועים לטיניים מאונכים בגודל 2, שיער אוילר שלא קיימים ריבועים מאונכים בגדלים 6, 10, 14 וכו'. ההשערה קיבלה חיזוק כאשר ב- 1901 הוכיח Gaston Tarry (באמצעות כוח גס) שלא קיים זוג ריבועים מאונכים בגודל 6. ואולם, בשנת 1959 מצאו Parker, Bose ו- Shrikhande זוג ריבועים מאונכים בגודל 10, והראו שקיים זוג כזה בכל גודל (פרט כמובן ל- 2 ו- 6).
<עריכה>
דוגמאות
להלן דוגמאות לכל המינים של ריבועים לטיניים, עד גודל 5.