בעיית וויל האנטינג

נקודת המוצא העלילתית של הסרט "סיפורו של וויל האנטינג" (וכאן אני עומד לגלות טיפה מפרטי העלילה – אבל לא משהו שלא מתגלה ממילא בעשר הדקות הראשונות של הסרט, ואיננו מהותי כל כך) היא חידה מתמטית שפרופסור ב-MIT נותן לסטודנטים בקורס מתקדם שלו, בתקווה שמישהו מהם יצליח לפתור אותה עד סוף הסמסטר ובכך יכנס להיכל התהילה. את החידה פותר כבדרך אגב דווקא השרת של הבניין, מה שחושף אותו כגאון מתמטי חבוי, וכל השאר היסטוריה. אולם מהי החידה שבחרו יוצרי הסרט לתת? מסיבות השמורות עמם, הם החליטו לאפשר לקהל לראות את החידה כתובה במלואה על הלוח, כמו גם את הפתרון. אציג את החידה, ולאחר מכן אסביר כיצד פותרים אותה.

ובכן, נתון גרף (ראו תמונה) ונשאלות עליו השאלות הבאות:

  1. מצאו את מטריצת השכנויות $latex A$ של הגרף $latex G$.
  2. מצאו את המטריצה שנותנת את מספר המסלולים מאורך 3 ב-$latex G$.
  3. מצאו את הפונקציה היוצרת של המסלולים מ-$latex i$ אל $latex j$.
  4. מצאו את הפונקציה היוצרת של המסלולים מ-$latex 1$ אל $latex 3$.

חידת וויל האנטינג

כבר בניסוח שלה, השאלה מרגישה יותר כמו תרגיל סטנדרטי ולא כמו אתגר מתמטי כביר. ואכן, כפי שאראה בקרוב, מדובר בשאלה פשוטה למדי בתורת הגרפים האלגברית – מה שקצת מוזר, בהתחשב בכך שהמרצה מציג את החידה בסרט בתור "Advanced Fourier System", בסוף שיעור שעוסק באנליזת פורייה (דהיינו, המרצה ממלמל משהו על משפט פרסבל, ששייך לאנליזת פורייה). אני סקרן לדעת איך התגלגלה השאלה הספציפית הזו לתסריט הסרט ואשמח אם מישהו שיודע זאת יספר.

הבה ונבהיר מה בעצם רוצים בשאלה הזו. ראשית, נותנים גרף $latex G$ על ידי ציור. גרף מורכב (כפי שניתן לראות בציור) מאוסף של עיגולים – "הצמתים" – וקווים שמחברים חלק מהם – "הקשתות". כך למשל בין הצומת 1 לצומת יש קשת אחת, בין 2 ו-3 יש שתי קשתות, בין 1 ו-3 אין אף קשת וכו'. מסלול בגרף מתחיל מצומת א', ואז מבצע סדרת "צעדים", כשכל צעד הוא מעבר מהצומת הנוכחי לצומת שמחובר לצומת הנוכחי בקשת. אם יש כמה קשתות בין שני צמתים, לרוב זה נחשב כאילו יש מספר דרכים לעבור בין שני הצמתים. כך למשל אפשר לקבל את המסלולים הבאים מצומת 1 לצומת 3 מאורך 2: ראשית הולכים מצומת 1 לצומת 2, ולאחר מכן הולכים מ-2 ל-3, אלא שיש שתי דרכים לעשות זאת כי יש שתי קשתות בין 2 ו-3. לכן יש שני מסלולים מאורך 2 מ-1 אל 3.

יש עוד שני מושגים להסביר – "מטריצה" ו"פונקציה יוצרת", שניהם מושגים בסיסיים יחסית במתמטיקה. מטריצה, בהקשר של השאלה הזו, ניתנת לתיאור בתור טבלה של מספרים. כשמדובר על מטריצת השכנויות של גרף מדובר על מטריצה ספציפית, שמקודדת בתוכה את מספר הקשתות בין כל שני צמתים בגרף. הכלל הוא פשוט: בשורה ה-$latex i$ והעמודה ה-$latex j$ כתוב מספר הקשתות שמחברות את הצמתים $latex i$ ו-$latex j$. לכן, מבט מהיר בגרף נותן לנו את המטריצה המבוקשת:

$latex A=\left(\begin{array}{cccc}0 & 1 & 0 & 1\\1 & 0 & 2 & 1\\0 & 2 & 0 & 0\\1 & 1 & 0 & 0\end{array}\right)$

עד כאן, שום דבר מורכב. התחכום מתחיל בשאלה הבאה – מי שלא בקיא בתורת הגרפים האלגברית (או בתחומים אחרים שבהם אותם רעיונות מופיעים, כמו למשל הילוכים מקריים בדידים) יכול לתהות מה הקשר בין מטריצה ובין מספר המסלולים ומה הולך כאן. כאן נכנסת לתמונה הפעולה של כפל מטריצות. מכיוון שמושג המטריצה, והמוטיבציה להגדרת כפל המטריצות באופן שבו הוא מוגדר, ראויים שניהם לפוסט שלם, לא אכנס לכך בינתיים אלא אניח כי ההגדרות מוכרות כבר לקורא (ועם מי שטרם יודעים הסליחה). כדי לראות כיצד כפל מטריצות עוזר לנו ניאלץ לשלוף את ההגדרה הפורמלית-טכנית של הכפל. אם נכפול את $latex A$ בעצמה, אז בקוארדינטה ה-$latex i,j$ של המכפלה נקבל את $latex \sum_{k=1}^{n}a_{ik}a_{kj}$. מה המספר הזה אומר? לכל $latex k$, $latex a_{ik}\cdot a_{kj}$ הוא מכפלה של מספר המסלולים מאורך 1 מ-$latex i$ ל-$latex k$, במספר המסלולים מאורך 1 מ-$latex k$ אל $latex j$. כלומר, זה מייצג את מספר הדרכים להגיע בשני צעדים מ-$latex i$ אל $latex j$ תוך מעבר בצומת הביניים $latex k$. כשסוכמים זאת על כל הערכים האפשריים של $latex k$ מקבלים את כל הדרכים לעבור מ-$latex i$ אל $latex j$ ב-2 צעדים.

באופן דומה אם נכפול את $latex A^{2}$ ב-$latex A$, הקוארדינטה ה-$latex i,j$ תהיה סכום של מכפלות, כשכל מכפלה היא של מספר הדרכים להגיע מ-$latex i$ אל $latex k$ בשני צעדים, ומ-$latex k$ אל $latex j$ בצעד אחד. אני מקווה שהרעיון ברור: לכל $latex m$ טבעי, הקוארדינטה ה-$latex i,j$-ית במטריצה $latex A^{m}$ מייצגת את מספר המסלולים מאורך $latex m$ מ-$latex i$ אל $latex j$ (אפילו עבור $latex m=0$ זה עובד: $latex A^{0}$ היא על פי הגדרה המטריצה שבה הכניסה ה-$latex i,i$ היא 1 לכל $latex i$, וה-$latex i,j$ היא 0 אם $latex i\ne j$, וזה מתאים ל"מסלול מאורך 0" מ-$latex i$ לעצמו שפשוט לא מכיל צעדים). מכאן שכדי לענות על שאלה 2 בסך הכל צריך לחשב את $latex A^{3}$. זה חישוב טכני לא מעניין במיוחד ואפשר לתת לתוכנות מחשב דוגמת מטלאב לבצע אותו. מקבלים:

$latex A^{3}=\left(\begin{array}{cccc}2 & 7 & 2 & 3\\7 & 2 & 12 & 7\\2 & 12 & 0 & 2\\3 & 7 & 2 & 2\end{array}\right)$

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

המשחק היה נהיה משעשע בהרבה אם היינו שואלים שאלות מהסגנון הבא: נניח שאנחנו יוצאים לטיול "אקראי" על הגרף, ובכל צעד אנחנו בוחרים באקראי את אחת מהקשתות שמחוברות לצומת הנוכחי שלנו. איך יראה הטיול? באילו צמתים נשהה זמן רב יחסית? וכן הלאה. זו דוגמה לסוג השאלות שניתן לשאול על שרשראות מרקוב בדידות, נושא מעניין לכשעצמו; והניתוח של התכונות הללו מתבצע בדיוק באמצעות ניתוח המטריצה $latex A$ שלנו, תוך שימוש בכלים של אלגברה לינארית. אלא שזה לא הכיוון שאליו הולכת שאלת וויל האנטינג ולכן לא אמשיך לדבר על כך כרגע.

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

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

ובכן, מה שמבקשים מאיתנו הוא הצגה מפורשת לפונקציה $latex f\left(x\right)=\sum_{n=0}^{\infty}b_{n}x^{n}$ כאשר $latex b_{n}$ הוא מספר המסלולים מ-$latex i$ אל $latex j$ מאורך $latex n$. אם נסמן ב-$latex \left[A\right]_{ij}$ את הכניסה ה-$latex i,j$ של המטריצה $latex i,j$ וננפנף בידיים ממש מהר, נקבל את החישוב הבא: $latex \sum_{n=0}^{\infty}b_{n}x^{n}=\sum_{n=0}^{\infty}\left[A^{n}\right]_{ij}x^{n}=\sum_{n=0}^{\infty}\left[\left(Ax\right)^{n}\right]_{ij}=\left[\sum_{n=0}^{\infty}\left(Ax\right)^{n}\right]_{ij}=\left[\frac{1}{1-Ax}\right]_{ij}$.

מה שעשיתי כאן היה להשתמש בוריאציה על הנוסחה הישנה והטובה לסכום סדרה הנדסית אינסופית מתכנסת: $latex 1+x+x^{2}+\dots=\frac{1}{1-x}$. כמובן שצריך להצדיק את השימוש בה עבור מטריצות, אבל אמרתי שאנפנף בידיים.

כעת השאלה היא האם באופן כללי בהינתן מטריצה $latex B$, יש נוסחה "יפה"עבור הכניסה ה-$latex ij$ בהופכית שלה, כלומר $latex \left[B^{-1}\right]_{ij}$? התשובה היא שכן (אם כי "יפה" זה עניין סובייקטיבי כאן) והיא מכונה "כלל קרמר". הכלל מסתמך על שני מושגים לא פשוטים – מטריצה מצורפת (Adjugate) ודטרמיננטה של מטריצה, ולכן עבור מי שאינו מכיר את המושגים הללו הנוסחה תיראה פשוט כמו אוסף של סימנים חסרי משמעות – אבל זה לא חשוב כל כך לבינתיים. הנקודה היא ששני היצורים הללו ניתנים לחישוב יחסית באופן פשוט. כעת, כלל קרמר אומר כי $latex B^{-1}=\frac{\mbox{Adj}B}{\det B}$ (כאן אנו מחלקים מטריצה – $latex \mbox{Adj}B$ – בסקלר – $latex \det B$). לכן $latex \left[B^{-1}\right]_{ij}=\frac{\left[AdjB\right]_{ij}}{\det B}$. אם רוצים לפשט את הביטוי עוד יותר צריך לחפור בהגדרה של $latex \mbox{Adj}B$: הכניסה ה-$latex ij$ של $latex \mbox{Adj}B$ מוגדרת בתור $latex \left(-1\right)^{i+j}M_{ji}$, כאשר $latex M_{ji}$ הוא המינור ה-$latex ji$-י של $latex B$ – הדטרמיננטה של המטריצה שמתקבלת ממחיקת השורה ה-$latex j$ והעמודה ה-$latex i$ של $latex B$. כאן כנראה וויל משתעמם ומשתמש בסימונים שאיני מכיר, כי הנוסחה הסופית שהוא כותב על הלוח היא $latex \frac{\det\left(B_{ij}\right)}{\det B}$ – אני משער שכוונתו זהה לכוונה שלי (למעשה, הוא לא כותב $latex B$ אלא $latex I-Ax$ כמו שכתבתי קודם – ולמעשה, אפילו לא את זה, אלא $latex I-zA$, שכמובן אומר את אותו הדבר בדיוק).

חידת וויל האנטיג - הפתרון

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

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

23 תגובות בנושא “בעיית וויל האנטינג”

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

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

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

  4. יכול להיות, השאלה היא איזו בעייה הם יכלו להציג? הרי הוא פותר אותה על הלוח. האם יש בעייה קשה מאוד שאפשר לפתור בכמה עשרות שורות של הוכחה ולא עשרות דפים?

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

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

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

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

  9. עד כמה שאפשר לראות לפי הפיתרון של וויל הבעיה הראשונה היא מציאת כל העצים בעלי 10 קודקודים כך שלא קיים בהם קודקוד עם דרגה 2 (לא הומומורפים לאף עץ עם 9 קודקודים).

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

  11. מאולץ מדי לדעתי. אם אני הייתי צריך לכתוב את שם השיעור על הלוח, הייתי בוחר "קומבינטוריקה אנומרטיבית", או "קומבינטוריקה אנליטית" (פחות טוב) או, כמו שאמרתי בפוסט, "תורת הגרפים האלגברית". בכל אחד מהמקרים השאלה עדיין מביכה בפשטות שלה – בערך עמוד אחד מהספר של Stanely מספיק כדי לפתור אותה.

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

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

  14. חפרתם יותר מדי זה רק סרט… למי אכפת מה רשמו על הלוח? גם אם היה נותן כחידה את לוח הכפל זה לא היה משנה.

  15. תענוג של פוסט, אני רק הייתי משנה את ההגדרה של פונקציות יוצרות ל-"הדבר ההוא מקומבינטוריקה שגרם לנו לשקול בחיוב לנטוש את האקדמיה, להחליף זהות, לרדת מהארץ ולשתות אקונומיקה".

    נקרא היום כי אני דווקא הבנתי את הכמות החריגה של כניסות לעמוד 🙁

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *