ניחושו המוטעה של אוילר

11/07/2005 ב- 17:53 | פורסם בהספרייה המדעית | סגור לתגובות על ניחושו המוטעה של אוילר

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

---

ליאונהרד אוילר (Leonhard Euler), יליד שוויץ, היה מתמטיקאי פורה למדי. כבר בגיל 29 פתר את בעיית הגשרים של קניגסברג, והניח את היסודות לתורת הגרפים. העיר קניגסברג היתה מחולקת לארבעה חלקים על ידי הנהר שעבר בה, ושבעה גשרים חיברו ביניהם. תושבי קניגסברג ניסו פעמים רבות וללא הצלחה, לחצות את כל שבעת הגשרים ולחזור לנקודת ההתחלה מבלי לחלוף על אותו גשר יותר מפעם אחת. רק בשנת 1736 נפתרה הבעיה בידי אוילר. הוא הוכיח שלא קיים מסלול סגור שעובר דרך כל הגשרים.

זוהי הבעיה המפורסמת של גשרי קניגסברג:

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

הנה דוגמה לריבוע קסם:

אוילר נהג למלא את משבצות הריבועים באותיות לטיניות (להבדיל מאותיות יווניות), ומשום כך מכנים אותם ריבועים לטיניים. מהו ריבוע לטיני? סודוקו, משחק המחשבה, הוא סוג של ריבוע לטיני מסדר 9.

הנה דוגמה לריבוע לטיני מסדר 4:

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

הנה ריבוע מסדר 4 המבוסס על אותיות יווניות:

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

הנה דוגמה לריבוע לטיני דיאגונלי מסדר 5:

e	d	c	b	a
c	b	a	e	d
a	e	d	c	b
d	c	b	a	e
b	a	e	d	c

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

הנה חידת קלפים עממית מהמאה ה-18: קחו את ארבעת המלכים, המלכות, הנסיכים והאסים של חפיסה כלשהי, וסדרו אותם בטבלה מרובעת בת 16 משבצות. עליכם להקפיד שכל קלף יופיע פעם אחת בלבד בכל שורה ובכל עמודה. בשלב הבא, קחו מן החפיסה את התלתנים, העלים, היהלומים והלבבות, והקפידו לסדרם כך שכל קלף שכזה יופיע פעם אחת בלבד, בצירוף עם אחד המלכים, המלכות, הנסיכים והאסים. ישנן אפשרויות רבות לפתרון החידה על פי ריבוע יווני-לטיני. אם נקפיד שגם באלכסון לא תהא כפילות מסוג זה שתיארנו, עדיין ישנם 72 פתרונות שונים.

זהו פיתרון אחד מיני רבים לחידת הקלפים:

בימיו של אוילר היה קל להוכיח שריבוע יווני-לטיני מסדר 2 הוא בלתי אפשרי. ריבועים מסדר 3, 4, 5 היו ידועים, אבל מה עם ריבוע מסדר 6? בעיה מעניינת זאת נקרתה לפני אוילר בשנת 1782, שנה לפני מותו: בששה גדודים שונים, ישנם ששה קצינים בעלי דרגות שונות. האם אפשר לסדר את 36 הקצינים במערך בן 6X6 משבצות, כך שבכל שורה ובכל עמודה יימצאו קצינים בעלי דרגות שונות ומגדודים שונים?

אוילר הוכיח שלבעיית הריבוע מסדר n יש תמיד פתרון, אם n הוא אי-זוגי או אם הוא זוגי ומתחלק ב-4. לעומת זאת, ניחש אוילר כי עבור n=6, 10, 14 אין ריבוע מסוג nXn, מכיוון שמספרים זוגיים אלה אינם מתחלקים ב-4. ואכן, בשנת 1901 הוכיח המתמטיקאי הצרפתי גסטון טארי (Gaston Tarry), כי אומנם נכון היה ניחושו של אוילר לגבי ריבוע מסדר 6. הוא עשה זאת על ידי בחינה מייגעת של כל אפשרויות הסידור של שש האותיות הלטיניות עם שש האותיות היווניות. אוילר סיים את מאמרו במילים: "בשלב זהו מסיים אני את חקירותיי בשאלת הקצינים, אשר על אף השימוש המעשי המועט בה, הביאה אותי להסתכלויות חשובות בתורת הצירופים, וכן לתיאוריה כללית של ריבועי קסם".

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

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

ריבוע יווני-לטיני, לפיכך, הוא מפת ניסויים לכל דבר. השורות מייצגות משתנה אחד, העמודות מייצגות את המשתנה השני, האותיות הלטיניות מייצגות את המשתנה השלישי, והאותיות היווניות מייצגות את המשתנה הרביעי. על פישר היה להשתמש בריבוע מסדר 7 וכך אמנם עשה. מחמת השוני האקראי בפוריות הקרקע בחלקות השונות, לא הופיעו בחישוב הסטטיסטי כל שיבושים.

בדרך דומה ניתן לתאר ניסוי ברפואה. אנו מבקשים לבדוק את השפעתם של חמישה מיני תרופות. לרשותנו עומדים חולים בחמש דרגות שונות של מחלה. כמו כן, הם משתייכים לחמש קבוצות של גיל, וגם לחמש קבוצות של משקל. ריבוע יווני-לטיני מסדר 5, שאת משבצותיו נבחר באקראי, הוא שישמש אותנו לתכנון המחקר. בדוגמה שלנו, תייצגנה השורות את קבוצות הגיל, העמודות תייצגנה את המשקל, האותיות הלטיניות את מיני התרופות, והאותיות היווניות את דרגות המחלה. הנה כי כן, חקירותיו של אוילר מסייעות בידנו לתכנן באופן יעיל כל מחקר מדעי. אך האם צדק בניחושו כי לא יתכן קיומו של ריבוע יווני-לטיני מסדר 10?

בפגישה השנתית של חברי אגודת המתמטיקאים בארצות הברית, שנערכה באפריל 1959, הראו שלושה מתמטיקאים מאוניברסיטת קרוליינה, פרקר (E.T. Parker), בוז (R.C. Bose) ושריקנד (S.S. Shrikhande), דרך לבניית ריבוע יווני-לטיני מכל סדר שהוא, מלבד מסדר 6, ובכך סתרו את ניחושו של אוילר לאחר 177 שנה.

זהו ריבוע יווני-לטיני מדרגה 10. הספרות 0-9 שמצד שמאל מייצגות אותיות לטיניות, והספרות 0-9 שמצד ימין מייצגות אותיות יווניות.

מעניין לציין ששיטת בנייתם של "שוללי אוילר" היתה מבוססת על בעיה מפורסמת במתמטיקה אלמנטרית הקרויה "בעיית התלמידות" שהציג תומאס קירקלמן (Thomas Kirkman) בשנת 1850: בבית הספר ישנן 15 תלמידות שנוהגות לצאת לטיול היומי שלהן בשלשות. איך ניתן לסדר את הטיולים הללו, כך שאף תלמידה לא תצעד במשך שבעת ימי השבוע יותר מפעם אחת עם כל תלמידה אחרת באותה שלשה?

הנה הפתרון לבעיית התלמידות:

ראשון	שני	שלישי	רביעי	חמישי	שישי	שבת
01, 06, 11	01, 02, 05	02, 03, 06	05, 06, 09	03, 05, 11	05, 07, 13	11, 13, 04
02, 07, 12	03, 04, 07	04, 05, 08	07, 08, 11	04, 06, 12	06, 08, 14	12, 14, 05
03, 08, 13	08, 09, 12	09, 10, 13	12, 13, 01	07, 09, 15	09, 11, 02	15, 02, 08
04, 09, 14	10, 11, 14	11, 12, 15	14, 15, 03	08, 10, 01	10, 12, 03	01, 03, 09
05, 10, 15	13, 15, 06	14, 01, 07	02, 04, 10	13, 14, 02	15, 01, 04	06, 07, 10

ואיך ריבוע לטיני קשור לסודוקו? כידוע, מתבקש שחקן הסודוקו למלא את התשבץ בספרות לפי כללי המשחק. סודוקו פתור כמו בדוגמה הבאה, הוא ריבוע לטיני לכל דבר. כללי הסודוקו דורשים שבכל אחד מתשעת הריבועים שמרכיבים את התשבץ, ישובצו כל הספרות בין 1 ל-9 מבלי שאף ספרה תופיע בו פעמיים.

ראו גם:

הסודוקו של פישר
סודוקו קסם חלקי: אתגר למתמטיקאים

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