השערת רייזר על ריבועים לטיניים

 ריבוע לטיני מסדר \({n}\) הוא ריבוע (מטריצה) מסדר \({n \times n}\) שממולא במספרים מ-\({1}\) עד \({n}\), כך שכל מספר מופיע פעם אחת בדיוק בכל שורה ופעם אחת בדיוק בכל עמודה.

riz1

ריבוע לטיני מסדר \({3}\).

טרנסוורסל בריבוע לטיני הוא אוסף משבצות, שנמצאות בשורות שונות, עמודות שונות, ומכילות מספרים שונים. גודל של טרנסוורסל הוא מספר המשבצות שבו. טרנסוורסל מגודל \({n}\) נקרא מלא.

riz2

טרנסוורסל מלא לריבוע הלטיני שלנו.

בתחילת שנות ה-\({70}\) ניסח מתמטיקאי אמריקני בשם רייזר (\({Ryser}\)) את ההשערה הבאה:

בכל ריבוע לטיני מסדר אי זוגי יש טרנסוורסל מלא.

ל-\({n}\) זוגי ההשערה לא נכונה. הסתכלו באיור. זהו לוח החיבור של המספרים מודולו (שארית) מ-\({4}\). אין בו טרנסוורסל מלא.

משפט 1 –  לוח החיבור של המספרים מודולו (שארית) מ-\({2k}\) הוא ריבוע לטיני, שאין לו טרנסוורסל מלא.

הוכחה: את העובדה שזהו ריבוע לטיני נשאיר כתרגיל. נוכיח רק שאין טרנסוורסל מלא. נניח שיש טרנסוורסל כזה. מכיוון שמופיעים בו כל המספרים בין 1 ל-\({2k}\), סכום איבריו הוא \({1+2+\ldots +2k}\), שעל פי הנוסחה לסכום של טור גיאומטרי שווה ל-\({\frac{(2k+1)2k}{2}=(2k+1)k}\). מצד שני, מכיוון שכל עמודה בלוח החיבור וכל שורה בלוח מיוצגות על ידי משבצת אחת בטרנסוורסל, ומכיוון שבכל משבצת מופיע סכום השורה והעמודה שלה, יוצא שסכום המספרים במשבצות הוא \({2(1+2+\ldots+2k)=(2k+1)2k}\). נזכיר שכל החישובים האלה הם מודולו (שארית מ-) \({2k}\). ההפרש בין שתי התוצאות בשתי דרכי החישוב השונות הוא \({(2k+1)(2k-k)=(2k+1)k}\), שהשארית שהוא משאיר בחלוקה ב-\({2k}\) היא \({k}\), שאינו \({0}\) מודולו \({2k}\). אם כן, יצאו לנו שתי תוצאות שונות – סתירה.

תלמיד תיכון ממקדוניה, בודן אסובסקי, הוכיח שהשערת רייזר נכונה ללוח החיבור של חבורות מסדר אי זוגי. מה ידוע על ההשערה? לא הרבה. \({Shor}\) ו-\({Hatami}\) הוכיחו שיש טרנסוורסל בגודל \({n – 5 \log_2^2n}\). זה יפה, אבל לא נותן רמז מדוע ההשערה נכונה. רמז יותר טוב ניתן על ידי שטיין, ששיער את הדבר הבא: בריבוע \({n \times n}\) שבו כל אחד מן המספרים \({1,2, \ldots ,n}\) מופיע \({n}\) פעמים יש טרנסוורסל מגודל \({n-1}\) (כלומר כמעט מלא).

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

riz3

אגב, בהשערת שטיין אין הבדל בין המקרה הזוגי והאי זוגי. התרגיל הבא מראה זאת:

תרגיל 1 –  לכל \({n}\) מצאו ריבוע \({n \times n}\) שמכיל כל אחד מן המספרים \({1, \ldots ,n}\) כל אחד בדיוק ב-\({n}\) משבצות, שאין לו טרנסוורסל מלא.

האם השערות כאלה חשובות? זה תלוי בטיב הפתרון. במקרה זה אני אישית מאמין שהפתרון יגלה מבנה עמוק, ויוביל לתובנות קומבינטוריות שיקרינו גם על תחומים אחרים.

תגובה אחת על השערת רייזר על ריבועים לטיניים

  • מאת עמי סגל‏:

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