סיפורו של ג'ורג' דנציג

זוכרים את הסרט "סיפורו של וויל האנטינג" (Good Will Hunting)? באחת הסצינות בתחילת הסרט משאיר המרצה בעיה על הלוח מחוץ לכיתה ומגלה שאלמוני הצליח לפתור אותה. המרצה משאיר בעיה קשה עוד יותר על אותו לוח, ולאחר השיעור הוא תופס על חם את וויל האנטינג, איש הניקיון, פותר את הבעיה השנייה. במציאות מוכר מקרה דומה - מדהים עוד יותר - שאולי שימש כהשראה לסצינה הנהדרת הזו. זהו סיפורו של ג'ורג' דנציג. אבל לפני כן, בכמה מילים על הבעיות שאותן פתר וויל האנטינג בסרט.

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



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

ג'ורג' דנציג בצעירותו

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

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

התזה של ג'ורג' דנציג התבססה על שני הפתרונות והוא יכול היה להגיש אותה כבר ב-1941, אלא שאז נכנסה ארצות הברית למלחמת העולם השנייה ודנציג החליט לסייע למאמץ המלחמתי. הוא שימש במהלך המלחמה כסטטיסטיקאי עבור חיל האוויר. כעבור חמש שנים חזר דנציג לברקלי והגיש את עבודת הדוקטורט. לאחר מכן פנה לעבוד עבור משרד ההגנה ושם פיתח ב-1947 את שיטת הסימפלקס לפתרון בעיות אופטימיזציה, שיטה שהקנתה לו את פרסומו. בשיטה זו ניתן לפתור בעיות של תכנות לינארי - מציאת מקסימום לביטוי לינארי מוגדר תחת אילוצים לינאריים. ביטוי לינארי מכיל רק קבועים ומשתנים בחזקה ראשונה, למשל 5x+4y, והאילוצים יכולים להופיע בבעיה כשוויונות או כאי-שוויונות. האלגוריתם של דנציג הוא אחד החשובים במדעי המחשב והוא משמש באופן נרחב ביותר עד ימינו אלו. רבים סבורים כי ועדת פרס נובל טעתה כשלא הכלילה אותו עם מקבלי הפרס בכלכלה בשנת 1975 שניתן לחלוצי התכנות הלינארי. אגב, הייחוד בשיטה של דנציג לפתרון הבעיה הוא הגישה ההנדסית - ייתכן שאלפי הבעיות שהוא פתר בילדותו עזרו לו לחשוב בכיוון זה. דנציג בילה שנים רבות באקדמיה: ב-1960 הוא קיבל משרת פרופסור בברקלי וכעבור שש שנים עבר לאוניברסיטת סטנפורד שבה נשאר עשרות שנים. הוא נפטר בשיבה טובה בשנת 2005.

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

לקריאה נוספת:
האם דמותו של וויל האנטינג מבוססת על חייו של ויליאם סיידיס? - ויליאם סיידיס (William Sidis) הוא גאון אמריקאי שחי במחצית הראשונה של המאה העשרים.
מאמר אודות ג'ורג' דנציג (pdf)

פעולת החיסור

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

עשיתי לי רשימה של כמה סוגי בעיות שכולן מובילות לחיסור:

1. גריעה - נתונה כמות של עצמים ולוקחים ממנה מספר עצמים. כמה נשאר?
2. הפרדה - נתונה קבוצה של עצמים שמתוכה חלק הם עצמים מסוג אחד. כמה עצמים בקבוצה הם מהסוג השני?
3. השוואה - בכמה קבוצת עצמים אחת גדולה/קטנה מהשנייה?
4. השוואת נפח או משקל - בכמה הנפח/המשקל של עצם אחד גדול/קטן מזה של עצם אחר?
5. תנועה אחורה - הולכים דרך מסוימת בכיוון אחד ואז חוזרים מרחק מסוים אחורה. באיזה מרחק מנקודת ההתחלה אנחנו נמצאים?
6. ירידה - עלינו לקומה מסוימת ואז ירדנו מספר קומות. באיזו קומה אנחנו עכשיו?
7. הפרש מרחקים - מהו הפרש המרחקים בין שתי נקודות שממוקמות לאורך הדרך? כמה קומות מפרידות בין קומה אחת לאחרת?
8. משך זמן - כמה זמן נמשכה פעולה שהתחילה בשעה מסוימת והסתיימה בשעה אחרת?
9. הפרש זמנים - מהו הפרש הזמנים בין שני שעונים המצביעים על שעות שונות? או בין שני זמנים שונים?
10. עודף - שילמנו סכום הגדול מערכו של המוצר. כמה עודף מגיע לנו?
11. פעולה הפוכה לחיבור - שימושי במשוואות אלגבריות.
12. חיבור של מספר שלילי.

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

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

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

מומלץ לקרוא גם את: המשמעויות השונות של החיסור ותרומתן לפיתוח החשיבה מאת תלמה גביש

על מתמטיקה, פיזיקה ופוליסמנטיות

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

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

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

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

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

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

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

חוק המספרים הקטנים

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

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

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

באותו הקשר, בשנת 1980 הגה חובב החידות המתמטיות מרטין גרדנר את "החוק החזק של המספרים הקטנים": אין מספיק מספרים קטנים על מנת למלא את כל הדרישות שבהן עליהם לעמוד. זהו שם הומוריסטי לתופעה שבה נתקלים חובבי חידות מתמטיות. נראה לעתים שסדרה של מספרים קטנים ממלאת חוקיות מסוימת, אבל אם ממשיכים הלאה החוקיות נשברת בסופו של דבר. למשל, ארבעת המספרים האי-זוגיים הראשונים הם המספר 1 או מספר ראשוני (1,3,5,7). אם ממשיכים את הסדרה רואים שכלל זה אינו נכון משום ש-9 אינו ראשוני. קיימות דוגמאות משעשעות נוספות ל"חוק" הזה.

שתי המלצות על בלוגים מתמטיים בעברית

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

לא מדויק של גדי אלכסנדרוביץ'. עוסק בנושאים מגוונים במתמטיקה ומדעי המחשב. מעמיק מאוד. חלק מהפוסטים דורשים ידע במתמטיקה גבוהה (על-תיכונית).

כנס למשחקי חשיבה

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

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