תאמל״ק לי
מי לא זוכר את "סיפורו של ויל האנטינג"? מאט דיימון גילם שרת במכון הטכנולוגי של מסצ'וסטס (MIT). בזמן ששטף את המסדרונות, הוא חלף על פני לוח שעליו הייתה כתובה בעיה מתמטית מתקדמת. הוא עצר והחל לפתור את הבעיה, תוך שהוא יוצר מבנים שנראו כבלתי קריאים של נקודות וקווים – עד שלפתע פרופסור למתמטיקה יצא מאולם ההרצאות וגירש אותו משם.
לקהל נאמר קודם לכן שהבעיה ההיא נועדה להיות קשה להפליא, כזו שדורשת שנים של חשיבה מומחית לפתרונה, ובכל זאת היא פוענחה במהירות על ידי השרת הנבון בגילומו של דיימון תוך רגעים ספורים. אבל כצפוי אלה הבלים הוליוודיים.
כי "סיפורו של ויל האנטינג" אולי מספר סיפור נהדר, אבל הוא לא מאוד מציאותי. למעשה, האתגר המתמטי אינו עומד בביקורת קפדנית. עם טקס פרסי האוסקר המתקרב, רבים נזכרים בזוכים מהעבר – כולל "סיפורו של ויל האנטינג". כך שאולי כדאי להעיף מבט מקרוב על הלוח בסרט שבשנת 1997 קטף תשע מועמדויות וזכה הן בפרס התסריט המקורי והן בפרס שחקן המשנה.
הסרט נוצר בהשראת סיפור אמיתי – שהוא הרבה יותר מרתק מגרסת האגדה ב"סיפורו של ויל האנטינג". הסיפור האמיתי מתמקד בג'ורג' דנציג, שיום אחד ייוודע כ"אבי התכנון הליניארי". דנציג לא תמיד היה סטודנט מצטיין. הוא טען שהתקשה באלגברה בחטיבת הביניים. אך הוא לא היה אדם מהשורה כשהאירוע שהעניק השראה לסרט התרחש. באותה עת, הוא היה סטודנט לתואר שני במתמטיקה.
בשנת 1939 הוא הגיע באיחור להרצאה שהעביר הפרופסור לסטטיסטיקה ג'רזי ניימן באוניברסיטת קליפורניה, ברקלי. ניימן כתב שתי בעיות על הלוח, ודנציג הניח שהן שיעורי בית. דנציג ציין שהמשימה נראתה קשה מהרגיל, אך הוא בכל זאת פתר את שתי הבעיות והגיש את פתרונותיו לניימן. כפי שהתברר, הוא פתר את מה שהיו אז שתיים מהבעיות הלא פתורות המפורסמות ביותר בסטטיסטיקה.
הישג זה היה מרשים למדי. לעומת זאת, הבעיה המתמטית שבה השתמשו בסרט ההוליוודי קלה מאוד לפתרון ברגע שלומדים מעט מהז'רגון.
למעשה, האתגר הוא כזה: שרטטו את כל העצים שאינם ניתנים לצמצום הומיאומורפי בגודל n=10. כאן יש לציין שני דברים. ראשית, הצגת האתגר הזה היא למעשה הדבר הקשה ביותר בו. זה די לא מציאותי לצפות מאדם מהשורה – ללא קשר לכישרונו המתמטי – להכיר את השפה הטכנית המשמשת לניסוח הבעיה. אבל זה מביא אותנו לדבר השני שיש לציין: ברגע שמתרגמים את המונחים הטכניים, המשימה עצמה פשוטה.
עם מעט סבלנות והדרכה, אפשר אפילו להטיל אותה על ילדים.
פתרון הבעיה מ"סיפורו של ויל האנטינג"
תחילה: אוצר המילים. במתמטיקה, עץ הוא סוג של גרף – כלומר, אוסף של נקודות המחוברות זו לזו. עצים, בפרט, אינם יכולים להכיל לולאות, כך שלא ניתן לחבר את הנקודות באופן שיגרום להן להיסגר לאחת. גודל העץ ניתן במונחים של מספר הנקודות, או הצמתים, בגרף. במקרה זה, אנו יודעים שעלינו לשרטט את כל גרפי העצים האפשריים עם 10 צמתים.
המונח "הומיאומורפי" מתייחס בעצם לרעיון שהצמתים ברשת זו תמיד עוקבים אחר רצף מסוים; הצורה המדויקת של העץ אינה חשובה כמו רצף החיבורים. כשמשרטטים חיבור בין צמתים א' וב', אפשר להפוך את הקישור הזה לארוך יותר או קצר יותר או מסובב מעט, וזה לא ישנה כל עוד המבנה הכללי של הרשת נשאר זהה. החלק החשוב הוא שא' מתחבר לב'.
כדי לחשוב על זה בדרך אחרת, דמיינו עץ בצורת X עם חמישה צמתים ועץ בצורת K עם חמישה צמתים. עצים אלו נחשבים לאותו עץ כיוון שמספר הצמתים ורצף החיבורים לא השתנו בין שתי הצורות. ו"בלתי ניתן לצמצום", במקרה זה, פירושו שכל צומת בגרף חייב להיות מחובר על ידי קו אחד או על ידי שלושה קווים או יותר, כך ששום צומת אינו מחובר על ידי שני קווים בלבד: אם צומת היה מחובר על ידי שני קווים בלבד, ניתן היה לצמצם אותו לקו יחיד.
אז בשפה פשוטה, המשימה היא לשרטט את כל העצים בעלי התכונות המפורטות שלכל אחד מהם 10 צמתים. ישנן כמה גישות לכך. לדוגמה, ניתן לכתוב תוכנת מחשב שפותרת את המשימה בחלקיק שנייה. או שניתן להתחיל לשרטט ביד את כל הגרפים המקיימים קריטריונים אלו. מתברר שייתכן שתזדקקו רק לכמה דקות של שרבוט אם תחליטו לבחור בדרך האחרונה.
כדי להדגים זאת, תוכלו תחילה לשרטט עץ המורכב מצומת מרכזי אחד המקרין החוצה תשעה חיבורים, מה שנותן לנו סך של 10 צמתים. עיצוב זה עומד בקריטריונים הנדרשים כי זהו אחד העצים הבלתי ניתנים לצמצום הומיאומורפי בגודל n = 10.
לאחר מכן, שרטטו עץ עם שמונה חיבורים – תגלו שעיצוב זה מוביל למבוי סתום כי לא תוכלו להוסיף צומת מבלי ליצור מחדש את העץ הקודם או להכניס קו שניתן לצמצום. עברו לשרטוט עץ שמתחיל בצומת שיש לו שבעה חיבורים. עדיין תצטרכו להציב שני צמתים נוספים, אך תוכלו לדמיין את הוספתם לאחד משבעת הצמתים שזה עתה שרטטתם. בשלב זה, אתם אמורים להיות מסוגלים להמשיך לשרבט את כל האפשרויות.
אם אתם מעדיפים גישה שיטתית עוד יותר – למרות שהיא עשויה לקחת לכם קצת יותר זמן, בהתאם לנוחות שלכם עם תורת הגרפים – פתרון חכם אחד כולל התחשבות באילו תנאים מתמטיים העצים חייבים לעמוד וייצוגם באמצעות משוואות.
לצורך גישה זו, אנו יכולים להגדיר את nk כמספר הצמתים n עם k חיבורים. מכיוון שהעץ צריך להיות בלתי ניתן לצמצום, אין מצב שבו n2 יכול להתקיים, ולכן n2 = 0. יתרה מזאת, אנו יודעים שלעץ חייבים להיות 10 צמתים בסך הכל – זה אומר שלעולם לא יהיה לכם n10 או n11, וכן הלאה. המקסימום הוא n9.
כעת נוכל לייצג את מה שאנו יודעים באמצעות נוסחה מתמטית:
(שימו לב שדילגנו על n2 כי אנו יודעים שהוא שווה ל-0).
ישנה מגבלה נוספת שנוכל לבטא. לעץ שלנו עם 10 צמתים יהיו בסופו של דבר 18 קווים, או חיבורים, ביניהם אם נספור באופן כזה שהקישור בין צומת א' לצומת ב' נספר פעמיים (אחד עבור א'-ב', והשני עבור ב'-א'). אנו יכולים להשתמש בכך כדי לבנות משוואה שבה נייצג כל חיבור וצומת בנפרד. לדוגמה, אם צומת מתחבר לצומת אחד אחר, הוא יוצר חיבור אחד: 1n1. אם צומת יחיד מתחבר לשלושה צמתים אחרים, ייווצרו שלושה חיבורים, כלומר 3n3, וכן הלאה. זה מוביל אותנו למשוואה הבאה:
כעת יצרתם שתי משוואות המכתרות ומגבילות את אפשרויות שרטוט העצים שלנו. אך עלינו לשלב אותן כדי לזהות את המונחים הרלוונטיים ביותר למשימה שלנו. ניתן לחסר את המשוואה הראשונה מהשנייה כדי לקבל: 2n3 + 3n4 + 4n5 + 5n6 + 6n7 + 7n8 + 8n9 = 8
משוואה זו משמשת כנקודת ייחוס לשרטוט העצים השונים שלכם. הרעיון הוא לקחת מונחים שביחד יהיו שווים ל-8 כאשר תחברו את המספר השלם הראשון שלהם, או המקדם. הביטו ב-8n9 למשל. זה אומר לנו שאנו זקוקים רק ל-n9 או n11 אחד כדי לבנות את העץ שלנו, מה שמתאים לשרטוט שבו לצומת יחיד יש תשעה חיבורים. אם תנסו לשרטט n8 או n11, תיתקלו בתרחיש המבוי הסתום, ללא עץ שעומד בקריטריונים שלנו. אם הייתם משתמשים במשוואה הזאת כייחוס, לא הייתם טורחים אפילו לנסות לשרטט אותו כי הייתם רואים שלא ניתן לשלב את 7n8 עם מונח אחר כך שהמספר הראשון בכל אחד מהם יהיה שווה ל-8.
אבל צומת עם שבעה חיבורים, n7, יכול לעבוד אם משלבים אותו עם n3, כלומר ניתן לשלב עץ עם שבעה חיבורים (המיוצג על ידי 6n7 במשוואה) ועץ עם שלושה חיבורים (2n3) כדי למצוא פתרון נוסף לבעיה. ותוכלו להמשיך בתהליך משם!
קיימות דוגמאות טובות יותר. אפשר להבין מדוע יוצרי הסרט "סיפורו של ויל האנטינג" נרתעו מעבודתו האמיתית של דנציג. הפתרון שהוא הגה לא היה קצר והעצים כנראה מושכים יותר ויזואלית עבור צלם קולנוע. ועדיין, יוצרי הסרט בחרו בבעיה המתמטית הספציפית הזו בצורה גרועה, אפילו עבור סרט הוליוודי. להיסטוריה של המתמטיקה יש סיפורים מדהימים רבים, כולל סיפורים אמיתיים של אנשים רגילים מהשורה שפותרים בעיה פתוחה, שיכולים להיות חומר נהדר לסרטים.
בתחום הגאומטריה, למשל, פריצות דרך רבות בנוגע לריצוף המישור הושגו על ידי אנשים שאפתניים שלא למדו מתמטיקה או תחום דומה. אחת מהן התרחשה בשנת 2022, כאשר טכנאי דפוס בדימוס בשם דייוויד סמית מצא סוף סוף את "אריח איינשטיין" המבוקש מזה זמן רב: מצולע שיכול למלא מישור לחלוטין ללא רווחים ומבלי שהתבנית הנוצרת תחזור על עצמה אי פעם…
