ארכיון חודשי: יוני 2010

משולש פסקל

פורסם בתאריך על ידי
10

אחד הדברים היפים במתמטיקה הוא האופן שבו אובייקטים שנראים תמימים בהתחלה מתגלים כבעלי תכונות רבות ומעניינות. במבט ראשון, קשה לחשוב שאוסף הפתרונות של משוואה מוזרה כמו \(y^{2}=x^{3}+ax+b\) יתגלה כבעל מבנה עשיר ומעניין מאין כמוהו, אך אוספי פתרונות שכאלו (שמכונים "עקומים אליפטיים") הם אובייקט שנחקר בצורה אינטנסיבית במתמטיקה המודרנית, והתפרסמו בפרט בגלל הקשר שלהם לפתרון בעיית המשפט האחרון של פרמה בת שלוש מאות השנים.

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

משולש פסקל

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

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

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

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

אם כן, כל מסלול שמגיע לתא מס' \(k\) בשורה מס' \(n\) הוא מסלול שיש בו בדיוק \(k\) צעדי "ימינה" (ו-\(n-k\) צעדי "שמאלה") וכל מה שנשאר לעשות הוא לבחור אילו \(k\) מתוך \(n\) הצעדים יהיו צעדי ה"ימינה"המדוברים – ולכן יש בדיוק \({n \choose k}\) אפשרויות.

יפה, אז הבנו יותר טוב מהו משולש פסקל – הוא משולש שמתאר בדיוק את מקדמי הבינום. האם למדנו מכך משהו חדש על מקדמי הבינום? בהחלט! מכיוון שכל תא הוא סכום של שני התאים שמעליו, קיבלנו את הנוסחה הבאה: \({n \choose k}={n-1 \choose k-1}+{n-1 \choose k}\). כמובן, יש אלף ואחת דרכים להוכיח את הנוסחה הזו; אבל רובן סתם טכניות ולא ציוריות כמו זו של משולש פסקל – ויותר מכך, זו של משולש פסקל עוזרת לזכור בעל פה את הנוסחה (ש-בינינו? היא די מכוערת למראה). בגלל שמדובר במשולש פסקל קל לזכור ששני המחוברים הם עם \(n-1\) "למעלה", שהרי מדובר על השורה שמעל השורה הנוכחית.

אם אתם בכל זאת רוצים הוכחה ישירה יותר לנוסחה שלמעלה, הנה אחת שמשתמשת בעיקרון החיבור בקומבינטוריקה: \({n \choose k}\) הוא מספר הדרכים לבחור \(k\) מספרים מבין המספרים \(1,2,\dots,n\). אפשר לפצל את הבחירה הזו לשתי בחירות נפרדות – או ש-\(1\) הוא אחד מ-\(k\) האיברים שאנו בוחרים, ולכן נותר לדבר על בחירה של \(k-1\) איברים מתוך \(n-1\) האיברים שאינם 1; או ש-\(1\) איננו אחד מ-\(k\) האיברים שאנחנו בוחרים ולכן נותר לדבר על מספר הדרכים לבחור \(k\) איברים מתוך \(n-1\) האיברים שאינם 1.

נעבור לדבר על עוד תכונות של משולש פסקל – שעל פי מה שראינו, הן בבסיסן תכונות של מקדמי הבינום. תכונה מעניינת אחת היא שבכל שורה שמספרה הוא ראשוני \(p\), כל אברי השורה (חוץ מה-1-ים שבקצוות) מתחלקים ב-\(p\) (הסיבה לכך – כזכור, \({p \choose k}=\frac{p!}{k!\left(p-k!\right)}\), מה שאומר בפרט שהמונה הוא כפולה של \(p\), אבל במכנה אין כפולות של \(p\) כי כל המספרים שם קטנים ממנו, ומכיוון ש-\(p\) ראשוני גם מכפלה של איברים במכנה לא תיתן לנו את \(p\)). זו תכונה שבפני עצמה נראית בלתי מזיקה ובלתי מעניינת, אבל היא הופכת לחשובה מאוד כאשר עוסקים במתמטיקה יותר מתקדמת (לסקרנים שלא חוששים מהרבה ג'יבריש: זה מראה שבשדה ממציין \(p\) מתקיים \(\left(x+y\right)^{p}=x^{p}+y^{p}\) ולכן הפונקציה \(\varphi\left(x\right)=x^{p}\) היא הומומורפיזם; למעשה זה אפילו הומומורפיזם עם שם מיוחד – "אנדומורפיזם פרובניוס", ובאלגברה קומוטטיבית ובתורת גלואה יש לו חשיבות לא מבוטלת).

עוד תכונה משעשעת ובלתי מזיקה היא שסכום השורה ה-\(n\)-ית במשולש הוא בדיוק \(2^{n}\). כדי לראות את זה כדאי להיזכר בנוסחת הבינום של ניוטון: \(\left(x+y\right)^{n}=\sum_{k=0}^{n}{n \choose k}x^{k}y^{n-k}\). מה קורה כאשר מציבים \(x=y=1\)? מקבלים בדיוק \(2^{n}=\sum_{k=0}^{n}{n \choose k}\), כשהסכום באגף ימין הוא בדיוק סכום האיברים של השורה ה-\(n\)-ית. גם לתכונה הזו ניתן לתת הוכחה קומבינטורית ישירה: מספר הדרכים לבחור תת קבוצה של איברים מתוך \(n\) איברים קיימים היא בדיוק \(2^{n}\) (אסביר מדוע בפוסט הבא), ומצד שני אפשר להשתמש כאן בעיקרון החיבור ולפצל את בחירת תת הקבוצה לבחירה של תת קבוצה מגודל 0, או תת קבוצה מגודל 1, או תת קבוצה מגודל 2 וכן הלאה.

אותו תעלול של הצבה בנוסחת הבינום של ניוטון נותן את התכונה הבאה: לכל שורה, סכום האיברים במקומות הזוגיים פחות סכום האיברים במקומות האי זוגיים הוא אפס (במקרה זה ההצבה היא \(x=1,y=-1\) – בדקו זאת!).

תעלול חביב במיוחד הוא זה: אם אתם רוצים לראות מהי השורה ה-\(n\)-ית במשולש פסקל, חשבו את \(11^{n}\). כך למשל תגלו ש-\(11^{4}=14641\) – בדיוק איברי השורה הרביעית (\(1,4,6,4,1\)). הסיבה לכך פשוטה למדי – כשכופלים מספר ב-11, מחברים אותו עם עצמו כשהוא מוזז בצעד אחד שמאלה. זה אומר שכל ספרה בתוצאה תהיה סכום של שתי הספרות הסמוכות "בשורה שמעליה". רק מה? צריך להיזהר כאן קצת. \(11^{5}=161051\) שלא נראה כלל כמו משולש פסקל, אבל זה נובע מכך שאנחנו משתמשים בבסיס ספירה 10 (כלומר, עם הספרות 0 עד 9 ותו לא), ואילו בשורה החמישית של משולש פסקל כבר יש מספרים גדולים מ-9 שלא ניתן לייצג באמצעות ספרה אחת. אם היינו מציגים את המספרים הגדולים הללו בבסיס אחר – משתמשים, למשל, באות \(A\) כדי לייצג את המספר 10 כספרה בודדת (זה דבר מקובל ולגיטימי לחלוטין – למשל, במחשבים, שפועלים על פי בסיס 16, אכן משתמשים ב-\(A\) למטרה זו, וביתר האותיות הלטיניות עד \(F\). אם אתם רואים כתובת מחשב מוזרה שכוללת בה גם אותיות (כחלק מקריסת המערכת), קרוב לודאי שאתם רואים מספר בבסיס 16), אז היינו מקבלים \(11^{5}=15AA51\).

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

הבינום של ניוטון

פורסם בתאריך על ידי
23

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

בשלב כלשהו בתיכון נלמדת הנוסחה הפשוטה הבאה: \(\left(a+b\right)^{2}=a^{2}+2ab+b^{2}\). למה? ככה. לפעמים גם נלמדת נוסחה יותר מסובכת: \(\left(a+b\right)^{3}=a^{3}+3a^{2}b+3ab^{2}+b^{3}\). כשהייתי בתיכון תיעבתי את הנוסחה הזו, עם החזקה השלישית – אף פעם לא זכרתי בדיוק איך היא הולכת ונאלצתי לבדוק בדף הנוסחאות. כעת, כשאני כותב את הפוסט, לא נזקקתי כלל לדף נוסחאות כלשהו – וזה לא שהזכרון שלי השתפר במיוחד או שאני משתמש בנוסחה הזו על בסיס יומיומי. אני מקווה שעד סיום הפוסט גם כל הקוראים יוכלו לכתוב את הנוסחה הזו "מהראש" וללא צורך בשום דף נוסחאות או אפילו חישובים ידניים.

הבינום של ניוטון הוא נוסחה כללית עבור ביטויים כאלו – ביטויים שנראים כמו \(\left(a+b\right)^{n}\), כאשר \(n\) הוא מספר טבעי כלשהו. כמובן שעולה מאליה השאלה בשביל מה זה טוב; קשה לתת לה תשובה, פשוט כי הבינום אינו מטרה בפני עצמה אלא כלי שצץ לעתים קרובות כחלק מחישובים מסובכים יותר – זה אחד מהדברים שפשוט "טוב לדעת". רק אציין שלרוב השימושים הם דווקא לא טכניים-חישוביים, אלא כחלק מהוכחה תיאורטית כללית (למשל, מציאת הנגזרת של פונקציה מהצורה \(f\left(x\right)=x^{n}\) כוללת שימוש בבינום). לא אציג את הנוסחה עדיין פשוט כי היא מפחידה במבט ראשון; קודם כל נבין מה הולך כאן ונגיע אליה באופן טבעי.

במתמטיקה באופן כללי הדרך הטובה להבין מקרה כללי היא לעתים קרובות דרך בחינת מקרים פרטיים פשוטים, אפילו פשוטים ברמה מגוחכת. \(\left(a+b\right)^{1}\) הוא פשוט \(a+b\), וזה לא מלמד אותנו הרבה; אבל \(\left(a+b\right)^{2}\) זה כבר סיפור שונה. איך באמת מגיעים לאותה נוסחה מפורסמת של \(a^{2}+2ab+b^{2}\)?

לצורך כך בואו ונחזור רגע ליסודות. תשכחו מהבינום – איך מבצעים את פעולת הכפל הבאה – \(\left(a+b\right)\cdot c\)? כאן בא לעזרתנו אחד מחוקי החשבון הבסיסיים ביותר – חוק הפילוג, שקובע פשוט ש-\(\left(a+b\right)c=ac+bc\).

השלב הבא הוא המכפלה \(\left(a+b\right)\left(c+d\right)\). גם כאן אפשר להשתמש בחוק הפילוג בדיוק באותו האופן כמו קודם, ולקבל \(\left(a+b\right)\left(c+d\right)=a\left(c+d\right)+b\left(c+d\right)\). כעת אפשר להשתמש בחוק הפילוג שוב (הפעם בגרסה שלו שאומרת ש-\(c\left(a+b\right)=ca+cb\)) ולקבל \(a\left(c+d\right)+b\left(c+d\right)=ac+ad+bc+bd\). עד כאן חשבון פשוט – מה הקשר לקומבינטוריקה?

ובכן, אני רוצה שנחשוב על המכפלה \(\left(a+b\right)\left(c+d\right)\) באופן שונה – בתור תהליך של בחירה. בפתיחת הסוגריים, כל מחובר שנקבל בסכום הסופי מתקבל מבחירה של איבר אחד בסוגר השמאלי, בחירה של איבר אחד בסוגר הימני, והכפלתם. כך \(ac\) מתקבל כשנבחר האיבר הראשון בכל זוג סוגריים, \(bd\) מתקבל כשנבחר האיבר השני, וכן הלאה. שימו לב לסדר שבו כתבתי את האיברים: כתבתי \(ac\) ולא \(ca\) (למרות ששני ערכים אלו שווים אלו לאלו) כדי להבליט את העובדה ש-\(a\) נבחר מהסוגריים השמאליים ואילו \(c\) מהסוגריים הימניים.

עכשיו בואו נעבור לטפל ב-\(\left(a+b\right)^{2}\), שהוא מקרה פשוט יותר מהמקרה הכללי: \(\left(a+b\right)^{2}=\left(a+b\right)\left(a+b\right)\) ואחרי פתיחת הסוגריים נקבל את הסכום \(aa+ab+ba+bb\). כעת אפשר לשפר את מראה הסכום הזה: את \(aa\) אפשר להחליף ב-\(a^{2}\), ובמקום להסתבך עם \(ab\) ו-\(ba\) אפשר להשתמש בחוק החילוף ולקבל \(ab+ba=ab+ab=2ab\). הנה כי כן הגענו ל-\(a^{2}+2ab+b^{2}\), אבל לדעתי יותר חשוב לזכור דווקא את התוצאה ה"גולמית": \(aa+ab+ba+bb\).

בואו נעבור לטפל במקרה קשה הרבה יותר: \(\left(a+b\right)^{3}=\left(a+b\right)\left(a+b\right)\left(a+b\right)\). כאן אפשר לחשוב על תהליך פתיחת הסוגריים כעל תהליך של בחירת שלושה איברים והכפלתם – איבר אחד מכל סוגר. התוצאה הסופית תהיה סכום שבו כל מחובר מתקבל מבחירת איבר מכל אחד מזוגות הסוגריים. אם נכתוב במפורש את כל התוצאות (קצת טרחני, אני יודע) נקבל: \(aaa+aab+aba+abb+baa+bab+bba+bbb\). האם תוכלו להגיד לי, בלי לספור, כמה מחוברים יש? זו כבר שאלה קומבינטורית לגמרי: יש שלושה זוגות סוגריים, ומכל זוג אנו בוחרים אחד משני איברים – על כן, לפי עיקרון הכפל, יש לנו \(2\cdot2\cdot2=8\) אפשרויות בחירה (כי הבחירה שלנו מורכבת משלושה שלבים שבכל אחד מהם יש שתי אפשרויות בחירה) ולכן יש שמונה מחוברים בסכום – עכשיו אפשר לבדוק זאת ידנית.

כעת, כיצד ניתן לפשט את הזוועה של שמונת המחוברים? את \(aaa\) אפשר להחליף ב-\(a^{3}\). את \(aab\) אפשר להחליף ב-\(a^{2}b\). גם את \(aba\) אפשר להחליף ב-\(a^{2}b\) וגם את \(baa\) אפשר להחליף ב-\(a^{2}b\). אם כן, כמה פעמים יופיע \(a^{2}b\) בסכום הסופי? כמספר הפעמים שבהן אפשר לבחור מבין שלושת הסוגריים פעמיים את \(a\), ופעם אחת את \(b\). אלו בדיוק שלוש פעמים – אפשר לחשוב על כך בשתי דרכים שונות: או שאנו בוחרים את שני זוגות הסוגריים שמהם ניקח \(a\) ואז ממה שנשאר לוקחים \(b\), או שבוחרים את הסוגר שממנו ניקח את \(b\) ואומרים שמשני הנותרים ניקח \(a\). בדרך השנייה ברור לגמרי שיש רק שלוש אפשרויות (יש שלושה זוגות סוגריים). בדרך הראשונה זה קצת פחות ברור ולכן הגיע הזמן לקרוא לעזרת הכלי שלמדנו בפעם הקודמת: מספר האפשרויות לבחור \(k\) איברים מתוך \(n\) הוא \(\frac{n!}{k!\left(n-k\right)!}\) – ביטוי שלצורך פשטות סימנו בסימון \({n \choose k}\), ואצלנו \(n=3\) ו-\(k=2\) כך שנקבל \(\frac{3!}{2!1!}=\frac{6}{2}=3\).

בואו נחזור לרגע אל \(a^{3}\) ידידנו – כמה פעמים הוא יופיע בסכום? כמספר הפעמים שבהן ניתן לבחור \(a\) בכל שלושת זוגות הסוגריים – אבל יש בדיוק רק בחירה אחת שכזו. פורמלית זה שווה למספר האפשרויות לבחור שלושה איברים מתוך שלושה: \({3 \choose 3}=1\).

כעת הגיע הזמן לבצע קפיצת מדרגה כלשהי ולהתחיל להכליל את כל מה שעשינו פה ולתאר אותו באופן אחיד יותר. כשאנו פותחים את \(\left(a+b\right)^{3}\), מה אנחנו מקבלים? איברים שצורתם הכללית היא \(a^{i}b^{j}\), כך ש-\(i+j=3\) (כי כל איבר מתקבל מבחירת שלושה איברים בדיוק – השאלה היא רק כמה מתוכם הם \(a\) וכמה מתוכם הם \(b\)). אם כן, אפשר לכתוב זאת בצורה יותר פשוטה: \(a^{i}b^{3-i}\). כעת נשאלת השאלה – כמה פעמים האיבר \(a^{i}b^{3-i}\) מופיע? זהו בדיוק מספר האפשרויות לבחור את \(a\) בדיוק \(i\) פעמים מתוך 3 זוגות הסוגריים האפשריות, כלומר \({3 \choose i}\). זה מוביל אותנו לניסוח האחיד הבא: \(\left(a+b\right)^{3}={3 \choose 0}a^{0}b^{3}+{3 \choose 1}a^{1}b^{2}+{3 \choose 2}a^{2}b+{3 \choose 3}a^{3}\).

אוקיי, עכשיו אתם ככל הנראה שואלים את עצמכם מה לעזאזל עשיתי כאן. במקום לקבל, כמו שהבטחתי, משהו פשוט ויפה קיבלתי ביטוי שנראה כמו זוועת עולם. אלא שאני טוען שהביטוי כלל אינו מזוויע, אחרי שעובר ההלם הראשוני, ויש בו יתרון גדול – קל לזכור אותו. שימו לב לכך שהוא מאוד תבניתי: סכום של איברים מהצורה \({3 \choose i}a^{i}b^{3-i}\) כשהדבר היחיד שמשתנה הוא ערכו של ה-\(i\). זה דבר שקל לזכור. לא באמת צריך לזכור מה ערכו המדוייק של כל מקדם, אלא רק שכל מקדם הוא מהצורה \({3 \choose i}\) עבור ה-\(i\) המתאים. כשכתבתי את הנוסחה שבתחילת הפוסט "מהראש", זה מה שהשתמשתי בו.

כעת אני רוצה לקפוץ קצת קדימה ולהציג סימון שבתיכון לא נהוג להשתמש בו (וחבל). כבר אמרתי שהנוסחה שלי ל-\(\left(a+b\right)^{3}\) היא סכום של איברים שכולם נראים כמעט אותו דבר: \({3 \choose i}a^{i}b^{3-i}\), כשהדבר היחיד שמשתנה הוא ה-\(i\). הדרך המתמטית לכתוב זאת היא באמצעות האות היוונית \(\Sigma\) (סיגמה גדולה) שבאה לציין את המילה "סכום" (בשפה המתאימה, כמובן…). הנה הסימון: \(\left(a+b\right)^{3}=\sum_{i=0}^{3}{3 \choose i}a^{i}b^{3-i}\).

מה יש לנו פה? ובכן, אחרי הסיגמה יש לנו את \({3 \choose i}a^{i}b^{3-i}\) שכבר הזכרתי מספיק – זהו האיבר הכללי של הסכום. איבר כללי במובן זה שכל מחובר בסכום נראה כמוהו, לאחר הצבה של ערך מתאים ב-\(i\). האות \(i\) נקראת האינדקס של הסכימה, והמספרים שכתובים מתחת ומעל לסיגמה באים לציין את הערכים שאותם \(i\) מקבל; \(i=0\) אומר שהערך הראשון ש-\(i\) מקבל הוא 0, וה-3 למעלה אומר שזהו הערך האחרון שהוא מקבל. המוסכמה היא שאלא אם נאמר במפורש אחרת, \(i\) מקבל רק ערכים שלמים, ולכן הסכום מתאר את מה שמקבלים כאשר מציבים באיבר הכללי את הערכים \(i=0,1,2,3\).

אני מקווה שסימן הסכימה ברור כעת ולא מפחיד; שאלה אחת שאולי התעוררה בכם היא למה לא לכתוב \(\sum_{0}^{3}{3 \choose i}a^{i}b^{3-i}\) וחסל – למה צריך את ה-\(i=\) למטה? התשובה היא שלא תמיד ברור מהו האינדקס – לפעמים (ונראה דוגמה ממש בקרוב) יש יותר ממשתנה אחד שמופיע באיבר הכללי, וצריך להבהיר מי משמש כאינדקס הסכימה. עם זאת אעיר שכשההקשר ברור, לעתים קרובות נהוג להשמיט פרטים מסימן הסכימה, עד כדי כך שלפעמים אפשר למצוא נוסחאות כמו \(\sum a_{i}\) וחסל – כאן השאלה אילו ערכים האינדקס מקבל תלויה לחלוטין בהקשר, וכותבי הטקסט מצפים שהקורא יוכל להסיק את המידע הזה בעצמו. באופן לא מפתיע, בטקסטי מבוא לרוב אין זוועות שכאלה.

אוקיי, אז טיפלנו בבינום עבור החזקות \(1,2,3\); המתמטיקאים נוהגים בשלב הזה לעבור לטפל ב-\(n\) כללי וזה גם בדיוק מה שאני אעשה, ובלי הרבה שהיות אכתוב את הנוסחה, שזהה לגמרי למה שקיבלנו עבור המקרה של חזקה שלישית: \(\left(a+b\right)^{n}=\sum_{i=0}^{n}{n \choose i}a^{i}b^{n-i}\). עצרו רגע ונסו להבהיר לעצמכם למה היא נכונה.

ובכן, למה הנוסחה נכונה? בדיוק אותם שיקולים כמו קודם. \(\left(a+b\right)^{n}\) ניתן לכתיבה כמכפלה של \(n\) זוגות סוגריים, ולכן התוצאה הסופית תהיה סכום של איברים שהתקבלו מבחירת \(a\)-ים ו-\(b\)-ים – סה"כ \(n\) פעמים עבור שניהם. אם \(i\) הוא מספר ה-\(a\)-ים שנבחרו, אז נקבל איבר מהצורה \(a^{i}b^{n-i}\), ויש לנו בדיוק \({n \choose i}\) דרכים שונות לבחור \(i\) \(a\)-ים, וזהו. מה שכתבתי כאן הוא כמעט הוכחה מתמטית, והוא בוודאי מבהיר היטב למה הנוסחה נראית כמו שהיא נראית ואיך זה קשור לקומבינטוריקה (ואם זה עדיין לא ברור – זו אשמתי, לא אשמת ההוכחה). לטעמי הוכחה זו (הגם שאינה פורמלית במאה אחוזים) טובה בהרבה מההוכחה ה"יבשה" לנכונות הבינום, שמשתמשת באינדוקציה מתמטית מזוויעה.

אם כן, זהו זה. נפתרה הבעיה הכללית של \(\left(a+b\right)^{2}\) ו-\(\left(a+b\right)^{3}\) וכל חזקה טבעית אחרת, והנוסחה הסופית היא קצרה ויפה להצגה (אבל חשבו כמה מזוויע יהיה לכתוב באופן מפורש את \(\left(a+b\right)^{13}\)!). כעת אני מקווה כי גם ברור מדוע \({n \choose i}\) נקראים "מקדמי הבינום" – מכיוון שהם המקדמים של הגורמים מהצורה \(a^{i}b^{n-i}\) בפיתוח נוסחת הבינום. אני גם מקווה שכעת ברור קצת יותר איך הקומבינטוריקה מתקשרת לתחומים אחרים במתמטיקה (כאן – אלגברה בסיסית) ומסייעת לנו להבין גם אותם.

מהי קומבינטוריקה?

פורסם בתאריך על ידי
19

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

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

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

קרוב לודאי שרבים מכם שואלים את עצמכם על הקומבינטוריקה בפרט את אותה שאלה שלעתים שואלים על המתמטיקה בכלל – למי אכפת? למי אכפת אם יש 113,332,442 צירופים אפשריים לפרוזן יוגורט בדוכן הקרוב, ולא סתם 113,332,441? מה המספר הזה נותן לנו בכלל? מה הטעם בכל זה?

ראשית כל יש לענות לכך שאכן, לרוב לא אכפת לנו מהמספרים המדוייקים. מה שמעניין, כאמור, הוא "קצב הגידול" של הבעיה, או סדר הגודל שלה. דוגמה קלאסית לכך היא הלוטו: חישוב ההסתברות לזכות בלוטו היא חישוב קומבינטורי פשוט (אנו רוצים לחשב את מספר כל התוצאות האפשריות שיכולות להתקבל בלוטו, ואם מספר זה הוא \(A\), אז ההסתברות לזכייה בלוטו היא \(\frac{1}{A}\), ובמילים – \(1\) ל-\(A\), למשל "1 לעשרה מיליון"). כאן המספר המדוייק באמת לא חשוב לנו, אבל חשוב לנו ההבדל שבין הסתברות של 1 ל-6 לזכות בלוטו כל שבוע (ואם הפרס לכל זוכה היה מיליון ש"ח, אז בהסתברות שכזו גם אני הייתי ממלא לוטו באדיקות), ובין הסתברות של 1 לכמה עשרות מיליונים (אני לא ממלא לוטו).

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

עם זאת, לפעמים אנחנו מתעניינים מאוד במספרים המדוייקים, עד לספרה האחרונה. סיבה מרכזית אחת לכך היא שמספרים מדוייקים מאפשרים לנו למצוא קשרים בין בעיות שנראות שונות מהותית. הנה דוגמה קלאסית: סדרה חוקית של סוגריים היא סדרת של סמלים שהם או \(")"\) (סוגר ימני) או \("("\) (סוגר שמאלי), כך שבשום שלב, בקריאה משמאל לימין של הסדרה, לא נוצר מצב שבו קראנו יותר סוגרים ימניים משמאליים (כלומר, לא "סגרנו" סוגריים שבכלל לא נפתחו). כך למשל הסדרה \(()(())\) היא חוקית ואילו \()(()\) אינה חוקית. לא קשה כל כך להראות שהסדרה \(a_{n}\) שבה \(a_{n}\) מייצג את מספר הסדרות החוקיות שמכילות \(n\) סוגריים שמאליים ו-\(n\) סוגריים ימניים מתחילה עם הערכים הבאים: \(1,2,5,14,42,132,429\).

נעבור לבעיה לחלוטין לא קשורה – שילוש של מצולע משוכלל. מצולע משוכלל עם \(n\) צלעות הוא מצולע שבו כל הצלעות וכל הזוויות הפנימיות שוות בגודלן. למשל: משולש שווה צלעות. למשל: ריבוע. למשל: משושה משוכלל, וכן הלאה. כשעוסקים במצולעים במדעי המחשב – בעיקר בגרפיקה – נוח לעתים קרובות לפרק אותם למשולשים על ידי מתיחת קווים בין קודקודים קיימים עד שהצורה חולקה כולה למשולשים (לפעולה זו קוראים שילוש – טריאנגולציה). נשאלת השאלה – כמה שילושים שונים קיימים למצולע בעל \(n\) צלעות? מכיוון שעבור \(n=1,2\) אין בכלל מצולעים בעלי \(n\) צלעות, אני "ארמה" טיפה: \(b_{n}\) יסמן את מספר השילושים של מצולע בעל \(n+2\) צלעות. והנה זה פלא: הסדרה \(b_{n}\) גם היא מתחילה עם הערכים \(1,2,5,14,42,132,429\). זה מייד מדליק אצלנו נורת איתות בראש – הייתכן שיש קשר בין שתי הבעיות, בעיית הזוגות החוקיים של סוגריים ובעיית הטריאנגולציה? וכדי לאמת את החשדות שלנו אנחנו מחשבים (באמצעות מחשב) עוד כמה ערכים של הסדרות – והנה, כל ערך חדש שאנו מחשבים אכן יהיה זהה. וזה מוסיף ומחזק את האמונה שלנו ששתי הסדרות הללו חד הן, עד לשלב שבו נטרח לקחת עט ונייר ולהוכיח את הקשר בין שתי הסדרות. ההוכחה עצמה אינה טריוויאלית אך גם אינה מסובכת מדי, והסדרה \(a_{n}\) היא סדרה כה מעניינת ומרכזית ומופיעה בעוד הקשרים רבים ושונים שהיא זכתה לשם מיוחד: "מספרי קטלן". למעשה, קיימת אפילו נוסחה סגורה עבורם, אך לא אציג אותה כעת.

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

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

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

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

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

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

מכאן ואילך ההמשך הוא באותה הרוח: יש 50 אפשרויות לבחירת הקלף השלישי, 49 לבחירת הרביעי, וכן הלאה. כשהגענו לקלף האחרון נותרה לנו רק בחירה אחת – שלו בלבד – ולכן יש אפשרות אחת בלבד. בסיכומו של דבר עיקרון הכפל ייתן לנו את התוצאה \(52\cdot51\cdot50\cdots3\cdot2\cdot1\). מספר זה ניתן לכתוב גם כ-\(1\cdot2\cdots52\) (הרי אין חשיבות לסדר ביצוע פעולות הכפל). מכיוון שדבר שכזה – הכפלה של כל המספרים מ-1 ועד \(n\) – היא דבר נפוץ למדי במתמטיקה (ובקומבינטוריקה בפרט) נהוג לתת לה שם וסימון מיוחד: למכפלה \(1\cdot2\cdots n\) (כאשר \(n\) הוא תמיד מספר טבעי חיובי) קוראים "\(n\) עצרת"ומסמנים אותה ב-\(n!\) (\(n\) ואז סימן קריאה – כמו רוב הסימונים, אין מאחוריו יותר מדי הגיון מחוכם אלא בעיקר קונבנציה שבחר מישהו והשתרשה במהלך השנים).

אם כן, יש \(52!\) ערבובים של חבילות קלפים, ובאופן כללי יש \(n!\) לסדר בשורה \(n\) איברים שכולם שונים זה מזה – לסידור שכזה קוראים "תמורה", ובעברית – פרמוטציה. למי שסקרן, הערך המספרי המדוייק של \(52!\) הוא \(80658175170943878571660636856403766975289505440883277824000000000000\). המספר העצום בגודלו הזה הוא הסיבה לעושר הרב שאפשר למצוא במשחקי קלפים – אין כמעט שום סיכוי שיתקבלו שני ערבובים זהים, ולכן שני משחקים זהים.

אבל רגע, אני בעצם משקר, כי בהרבה משחקים אין חשיבות גדולה עד כדי כך לסדר החבילה. בואו ניקח לדוגמה את משחק הברידג': מחלקים את 52 הקלפים לארבעה שחקנים, 13 קלפים לכל שחקן. אין חשיבות לשאלת הסדר שבו כל שחקן קיבל את הקלפים, אלא רק לשאלה אילו קלפים הוא קיבל. אם כן, הבה ונשאל שאלה אחרת – בכמה דרכים שונות אפשר לבחור 13 קלפים מתוך חבילה של 52 קלפים אם אין חשיבות לסדר שבו הקלפים נבחרים?

עם הבעיה הזו אפשר להתמודד בעזרת הכלי שכבר רכשנו – מספר הפרמוטציות של \(n\) איברים. הבה ונניח ש-13 הקלפים נבחרים באופן הבא: ראשית מערבבים את החבילה, וכעת נותנים לשחקן את 13 הקלפים הראשונים בערבוב. אחרי שנותנים לו אותם הסדר הפנימי של הקלפים "נמחק", ולכן אם נספור כל ערבוב של החבילה באופן שונה, נבצע ספירה כפולה. מכיוון שזה מבלבל קצת בהתחלה, הבה ונביט בדוגמה פשוטה יותר: נניח שיש לנו חבילה שכוללת ארבעה קלפים בלבד: \(\mbox{A,K,Q,J}\), ושהשחקן רוצה לקבל שניים מהם. כבר את ארבעת הקלפים הללו ניתן לערבב בצורות רבות – 24, ליתר דיוק – ולכן לא אראה את כולן אלא אשאל שאלה אחרת: בכמה דרכים שונות אפשר לערבב את החבילה כך שהשחקן יקבל את \(\mbox{A,K}\)?

ובכן, אלו הן האפשרויות (שתי האותיות שמצד שמאל הן מה שהשחקן יקבל): \(\mbox{AKQJ,AKJQ,KAQJ,KAJQ}\). ספרנו ארבע פעמים חלוקה שהיינו אמורים לספור רק פעם אחת. איך אפשר לנטרל זאת? הצעד הראשון יהיה לשים מעין "מחיצה" שתפריד בין מה שהשחקן מקבל ומה שלא: \(\mbox{AK|QJ,AK|JQ,KA|QJ,KA|JQ}\). כעת נשאל את עצמו – מה קורה מכל אחד מעברי המחיצה? בצד שמאל אנחנו "בוחרים" את אחת משתי הפרמוטציות האפשריות של האיברים \(\mbox{A,K}\), ובצד ימין אנו "בוחרים" את אחת משתי הפרמוטציות האפשריות של האיברים \(\mbox{J,Q}\). בצורה הזו מתקבלות כל האפשרויות לבנות חלוקה של \(\mbox{A,K,Q,J}\) שבה \(\mbox{A,K}\) בצד שמאל ו-\(\mbox{Q,J}\) בצד ימין.

חזרה לבעיה שלנו – כאן יש 13 קלפים בצד שמאל, ו-39 קלפים בצד ימין. לכן יש \(13!\) אפשרויות לבחור סידור לקלפים בצד שמאל, ו-\(39!\) אפשרויות לבחור סידור לקלפים בצד ימין, ולכן על פי עקרון הכפל יש \(13!\cdot39!\) אפשרויות לבחור סידורים לכל הקלפים גם יחד כל עוד תובעים ש-13 הקלפים שבצד שמאל ישארו כולם בצד שמאל. במילים אחרות – לכל בחירה של \(13\) קלפים, יש בדיוק \(13!\cdot39!\) ערבובים של החבילה שבה \(13\) הקלפים הללו הם אלו שנבחרים.

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

אם כן, אם אנחנו יודעים את כמות הרגליים בעדר, ואנו יודעים שלכל כבש ארבע רגליים, משמעות הדבר היא שספרנו כל כבש ארבע פעמים, ולכן כדי לקבל את מספרם של הכבשים צריך לחלק את מה שספרנו ב-4. כך גם בדוגמה שלנו: יש \(52!\) ערבובים שונים של החבילה – זה מספר הרגליים; וכל חלוקת \(13\) קלפים נספרה \(13!39!\) פעמים – זה מספר הרגליים שיש לכבש; ולכן יש בסך הכל \(\frac{52!}{13!39!}\) חלוקות שונות. גם זה מספר עצום – \(635013559600\), אבל הוא קטן משמעותית מ-\(52!\).

באופן כללי אם יש לנו \(n\) אובייקטים שונים ואנו רוצים לבחור מתוכם \(k\) אובייקטים בלי חשיבות לסדר הבחירה, אז אותו החשבון מראה שיש \(\frac{n!}{k!\left(n-k\right)!}\) אפשרויות לעשות זאת. גם לביטוי זה יש סימון מקוצר: "\(n\) בחר \(k\)", או \({n \choose k}\) (שימו לב – זה אינו שבר!). היצור הזה מכונה גם "מקדם הבינום" בשל הקשר שלו לבינום של ניוטון – נוסחה כללית לביטויים מהצורה \(\left(a+b\right)^{n}\); ארחיב על כך בפוסט הבא בנושא.

איך בוטל "איך בוטלה המתמטיקה" – סוף דבר

פורסם בתאריך על ידי
20

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

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

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

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

למשמע התשובה היה פון-שנאוצר משיב בסיפור עלילה מוזר, רצוף במספרים, שהסתיים תמיד בשאלה (שהייתה השאלה האחרונה שיוהנס היה מעלה בדעתו).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

כך בוטלה המתמטיקה.

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

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

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

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

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

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

אני לא ממליץ על הספר.

שברים משולבים, ולמה הם מגניבים (חלק 2)

פורסם בתאריך על ידי
10

בפוסט הקודם הצגתי את השברים המשולבים – שברים מהצורה הכללית \(a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\dots}}}\) שכזכור, העדפתי לסמן בתור \(a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\frac{1}{a_{3}+\dots}\). מלמלתי משהו על כך שהם מעניינים במיוחד כאשר משתמשים בהם לייצג מספרים ממשיים אי רציונליים, ואז שקעתי בערב רב של חישובים ונוסחאות. הנה השורה התחתונה של אותם חישובים: אם \(\alpha\) הוא מספר ממשי כלשהו ומציגים אותו כשבר משולב אינסופי, אז ניתן לדבר על סדרת הסכומים החלקיים \(\frac{A_{n}}{B_{n}}\) שמתקבלים כאשר קוטמים את השבר המשולב לאחר ההגעה לאיבר \(a_{n}\). הסתבר שלסדרה הזו כמה תכונות מעניינות למדי: ראשית, תת-הסדרה של האיברים במקומות הזוגיים היא עולה, ואילו תת-הסדרה של האיברים במקומות האי זוגיים היא יורדת; שתי תת-הסדרות הללו מתכנסות לאותו איבר, ושלא במפתיע, איבר זה הוא \(\alpha\); וקצב ההתכנסות הוא ריבועי, במובן זה ש-\(\left|\alpha-\frac{A_{n}}{B_{n}}\right|<\frac{1}{B_{n}B_{n+1}}\). כדי להראות למה תוצאות אלו (ואחרות שאציג בהמשך) הן מעניינות אני רוצה להשוות את השברים המשולבים לדרך ה"רגילה" שבה אנחנו מייצגים מספרים ממשיים – השיטה העשרונית.

בשיטה העשרונית מספרים מיוצגים באמצעות טור חזקות: \(\alpha=\sum_{n=-\infty}^{k}a_{n}10^{n}\). כך למשל \(342.56\) זו פשוט דרך מקוצרת לכתוב את טור החזקות \(3\cdot10^{2}+4\cdot10^{1}+2\cdot10^{0}+5\cdot10^{-1}+6\cdot10^{-2}\). היתרון הגדול של שיטת ייצוג זו היא שאנו נזקקים רק ל-10 ספרות (\(0,1,\dots,9\)) כדי לייצג כל מספר ממשי שהוא. כמובן, הבחירה ב-10 היא שרירותית ויכלנו להשתמש גם בבסיסי ספירה אחרים, אך גם בהם הייתה נשמרת אותה תכונה – אנו זקוקים רק למספר סופי של ספרות כדי לייצג כל מספר ממשי.

צריך להיזהר כאן – כשאני אומר "מספר סופי של ספרות" הכוונה היא שאיני זקוק ליותר מאשר \(0,1,\dots,9\) כדי לייצג כל מספר, אבל אני בהחלט עלול להזדקק לחלק מהספרות אינסוף פעמים. כך למשל את המספר \(\frac{1}{3}\) אני יכול לכתוב בבסיס עשרוני רק בתור \(0.333\dots\), כש-3 הנקודות פירושן שהמספר נמשך עוד ועוד באותה הצורה לנצח (כלומר, סדרה אינסופית של 3-ים). מבחינה פורמלית אין כאן בעיה – חשבון אינפיניטסימלי בסיסי מראה כי \(\sum_{n=1}^{\infty}\frac{3}{10^{n}}=\frac{1}{3}\) (שימו לב שכתבתי את הטור כעת בצורה קצת יותר פשוטה, כי אין לי חזקות חיוביות). גם מבחינה מעשית אפשר איכשהו "לסלוח" לכך שצריך לכתוב אינסוף ספרות, מכיוון שלא באמת צריך – הייצוג \(0.333\dots\) כבר כולל את כל האינפורמציה על המספר. הוא אומר שיש לנו אפס, ואחריו סדרה אינסופית של 3-ים. האינפורמציה הזו מזהה את המספר בצורה מושלמת.

לרוע המזל, באופן כללי זה לא יכול לקרות, כפי שמראים טיעונים בסיסיים מתורת הקבוצות. לא קשה להראות שיש רק מספר בן מניה של ייצוגים סופיים למספרים כל עוד מגבילים את סט האותיות שבהן אנו משתמשים להיות סופי (כמו במקרה זה – הסימנים המותרים היחידים הם ספרות, נקודה עשרונית ושלוש נקודות -\(\dots\); יש דרך סימון מעט יותר מדוייקת למספרים עשרוניים שבה יש קו מעל רצף הספרות שחוזר על עצמו לנצח, אבל גם הוא סובל מאותה מגבלה), אבל מספרם הכולל של המספרים הממשיים אינו בן מניה. אינטואיטיבית, למי שלא מכיר מושגים אלו – יש אינסוף מספרים ממשיים ויש אינסוף מספרים שניתן לייצג בשיטה העשרונית באופן מחזורי, אבל האינסוף של הממשיים "גדול יותר" מהאינסוף של המספרים המחזוריים (במובן מתמטי פורמלי ומדוייק לחלוטין) כך שהמסקנה היא שאת רוב המספרים הממשיים לא ניתן לייצג בשיטה העשרונית באופן מחזורי. צריך לכתוב אינסוף ספרות – אבל זה כבר משהו שאנחנו לא מסוגלים לכתוב על נייר. לכן כשכותבים את פאי, כותבים \(\pi=3.14159265\dots\) – כלומר, כותבים חלק מהספרות הראשונות, ואז מתייאשים וכותבים שלוש נקודות שבאות לציין "זה נמשך ונמשך, אבל לא באופן שבו קבוצת ספרות חוזרת באופן מחזורי על עצמה". לא קשה להראות שהסיטואציה הזו מפרידה בין מספרים רציונליים ואי רציונליים: מספר הוא רציונלי אם ורק אם הייצוג העשרוני שלו הוא מחזורי (גם חזרה אינסופית של אפסים נחשבת למחזורית). כבר \(\sqrt{2}\) לא ניתן להצגה באופן מחזורי בבסיס עשרוני.

עוד בעיה מוזרה למדי של הייצוג העשרוני היא שיש מספרים שניתן לייצג בשתי דרכים שונות, כשהדוגמה המפורסמת ביותר היא \(1\) ו-\(0.999\dots\), שכבר הקדשתי לה פוסט. הבעיה אמנם נגמרת כאן – הסיטואציה היחידה שבה יש ייצוג כפול שכזה היא במספרים שבאחד מדרכי הייצוג שלהם הם מסתיימים בסדרה אינסופית של 9-ים, אבל היא קיימת בכל ייצוג על פי בסיס ספירה כלשהו (למשל, בבסיס 7 הבעיה הייתה עם מספרים שמסתיימים ב-\(666\dots\)).

לסיום, נשאלת השאלה מה קורה כאשר קוטמים את הייצוג העשרוני האינסופי אחרי מספר סופי של ספרות. למשל, אם ניקח את \(\pi\) ואת הייצוג העשרוני שלו, ואז נכתוב את הקירוב הבא: \(\pi\approx3.141\). מה גודל ה"טעות" שלנו? ובכן, היא המספר \(0.00059265\dots\). אם נעבור לכתיב של מספרים רציונליים, לקחנו את הקירוב \(\frac{3141}{10^{3}}\) ונותרנו עם טעות מסדר גודל שהוא בערך \(\frac{6}{10^{4}}\) ("בערך", כי כמובן שלא ניתן להציג את ערכה של הטעות במדוייק בתור מספר רציונלי – זה היה מראה ש-\(\pi\) עצמו רציונלי). במילים – סדר הגודל של הטעות הוא חצי מהמכנה בקירוב שלנו. זה לא הקירוב הכי מוצלח בעולם, וכדי לראות זאת נצטרך להבין קודם כל איך נראה קירוב מוצלח. שלא במפתיע, זה יהיה הקירוב שמספקים לנו השברים המשולבים.

ה"בעיה" הגדולה בשברים משולבים שמייצגים מספרים ממשיים היא שה"ספרות" שלנו אינן חסומות: עבור כמעט כל המספרים הממשיים, הייצוג שלהם כשבר משולב \(a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\frac{1}{a_{3}+\dots}\) יקיים את התכונה שסדרת ה-\(a_{n}\)-ים אינה חסומה. זה לא סוף העולם, כי כל \(a_{n}\) בעצמו מיוצג בפועל כסדרה סופית של ספרות בבסיס עשרוני, כך שעדיין ניתן לחשוב על שבר משולב כאילו הוא משתמש במספר סופי של ספרות כדי לייצג כל מספר ממשי.

לעומת הבעיה הזו, שתי ה"בעיות" הבסיסיות שהצגתי של השיטה העשרונית לא קיימות: ראשית, השבר המשולב שמייצג כל מספר ממשי הוא יחיד. אין עיוותיים סטייל \(1=0.999\dots\). שנית, כל מספר רציונלי מיוצג על ידי שבר משולב סופי. כבר אין עיוותים סטייל \(\frac{1}{3}=0.333\dots\). זה מעלה מייד את השאלה המסקרנת הבאה – עבור ייצוג עשרוני, מחזוריות גררה רציונליות; מה האנלוג עבור שברים משולבים? האם יש אפיון פשוט לשברים משולבים מחזוריים? התשובה היא כן, וזוהי אולי התוצאה הכי מרהיבה כאן (שמיוחסת ללגראנז'): השבר המשולב של \(\alpha\)הוא מחזורי אם ורק אם \(\alpha\) הוא פתרון של משוואה ריבועית במספרים שלמים – יצור כזה מכונה באנגלית Quadratic Number. כך למשל \(\sqrt{2}\) הוא הפתרון של המשוואה הריבועית בשלמים \(x^{2}-2=0\) ולכן השבר המשולב שלו הוא מחזורי: \(\sqrt{2}=1+\frac{1}{2+}\frac{1}{2+}\frac{1}{2+\dots}\). זו תוצאה מעניינת במיוחד למי ש(כמוני) אי רציונליות התערבבה אצלו בראש איכשהו עם "חוסר מחזוריות". שברים משולבים מאפשרים לנו לייצג חלק מהמספרים האי רציונליים באופן מחזורי למהדרין, שמציג בניית קירוב שלהם באמצעות ארבע פעולות החשבון בלבד.

הסקרנים ביותר מכם אולי תוהים כעת – אם שבר משולב אינסופי הוא תמיד אי רציונלי, מהו המספר האי רציונלי (ואי רציונלי תמיד מזוהה אינטואיטיבית עם "מסובך" ברמה מסויימת) שמתואר באמצעות השבר המשולב הפשוט ביותר – \(1+\frac{1}{1+}\frac{1}{1+\dots}\)? ברור שזה לא יהיה \(\sqrt{1}\) שהוא רציונלי ולכן מיוצג על ידי שבר משולב סופי (\(1\)), אז מה כן? הבה ונסמן לרגע \(a=1+\frac{1}{1+}\frac{1}{1+\dots}\); אם כן, לא קשה לראות ש-\(a-1=\frac{1}{a}\) (אם קשה לכם לראות זאת, נסו לרגע לכתוב את השבר המשולב "כמו שהוא באמת" ולא בטיפוגרפיה המפושטת שלי – תראו מייד שבמכנה יש לנו שוב פעם את \(a\)). על ידי כפל ב-\(a\) והעברת אגפים מקבלים שמתקיים \(a^{2}-a-1=0\). המשוואה הזו אולי לא מוכרת לכם, אבל הפתרון החיובי שלה מפורסם מאוד: המספר \(\phi=1.61803\dots\) הידוע בכינוי "יחס הזהב". תשכחו מהפרתנון או מהפרופורציות המושלמות של גוף האדם – הנה לכם מקום שבו יחס הזהב מופיע באמת ובתמים וללא שום ספק, ובאופן הכי טבעי שרק אפשר.

אגב, אולי אתם זוכרים מהפוסט הקודם שבהינתן שבר משולב \(a_{0},a_{1},a_{2},\dots\), סדרת הסכומים שמתכנסת אליו \(\frac{A_{n}}{B_{n}}\) קיימה את נוסחת הנסיגה \(A_{n}=a_{n}A_{n-1}+A_{n-2}\) ו-\(B_{n}=a_{n}B_{n-1}+B_{n-2}\). עבור יחס הזהב \(a_{n}=1\) תמיד, ולכן נקבל את נוסחאות הנסיגה \(A_{n}=A_{n-1}+A_{n-2}\) ו-\(B_{n}=B_{n-1}+B_{n-2}\) שנבדלות רק בערכים ההתחלתיים: \(A_{0}=1,A_{1}=2\) ואילו \(B_{0}=1,B_{1}=1\). אלו הן נוסחאות הנסיגה של מספרי פיבונאצ'י, והשברים המשולבים מראים לנו מיידית שהסכומים החלקיים הם מהצורה \(\frac{F_{n+1}}{F_{n}}\) כש-\(F_{n}\) הוא מספר פיבונאצ'י ה-\(n\)-י. זוהי דרך פשוטה לראות את הטענה המוכרת שיחס הזהב הוא היחס שאליו שואפים מספרי פיבונאצ'י (כלומר, "פי כמה" גדול מספר פיבונאצ'י ביחס לקודמו בסדרה).

עוד שאלה שאולי אתם שואלים את עצמכם היא מדוע אנחנו מגבילים את עצמנו לדיבורים על מחזוריות בלבד. האם לא ייתכן שבר משולב שבו יש תבנית ברורה כלשהי לאיברים, גם אם אינה מחזורית? התשובה חיובית עבור מקרים מסויימים, כשהדוגמה הבולטת היא \(e\): השבר המשולב שלו היא \(e=2+\frac{1}{1+}\frac{1}{2+}\frac{1}{1+}\frac{1}{1+}\frac{1}{4+}\frac{1}{1+}\frac{1}{1+}\frac{1}{6+\dots}\). כלומר, אחרי ה-\(2,1\) הראשוניים יש לנו סדרת מספרים מהצורה \(2,1,1,4,1,1,6,1,1,\dots\) וכן הלאה. זו איננה מחזוריות במובן הרגיל של המילה, אבל בהחלט יש כאן תבנית פשוטה ויפה (אגב, יש עוד דרכים רבות אחרות להציג את \(e\) באמצעות פעולות החשבון באופן שאינו מחזורי אך הוא מאוד תבניתי – הדרך הפשוטה ביותר היא זו שנובעת מטור טיילור שלו, \(e=\sum_{n=0}^{\infty}\frac{1}{n!}\)).

עבור פאי אין תבנית שכזו, אבל אם עוברים לדיבור על שברים משולבים מוכללים, שבהם לא חייב להופיע 1 ב"מונים", דווקא יש תבניות יפות, למשל \(\pi=\frac{4}{1+}\frac{1^{2}}{2+}\frac{3^{2}}{2+}\frac{5^{2}}{2+}\frac{7^{2}}{2+\dots}\). לא נכנסתי לתיאוריה שמאחורי שברים משולבים מוכללים שכאלו שכן היא מסובכת מעט יותר, אבל אני מניח שהעיקרון ברור.

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

בואו נעבור לדבר על איכות הקירובים שמספקים השברים המשולבים. ניקח את השבר המשולב הרגיל של \(\pi\): \(\pi=3+\frac{1}{7+}\frac{1}{15+}\frac{1}{1+}\frac{1}{292+\dots}\). אם נחשב את הסכומים החלקיים, נקבל את סדרת הקירובים הבאה עבור \(\pi\): \(3,\frac{22}{7},\frac{333}{106},\frac{355}{113},\dots\). בואו ננסה להבין עד כמה קירובים אלו טובים.

הקירוב \(\frac{22}{7}\) היה ידוע כבר מהעת העתיקה והוא "קירוב בית הספר" לפאי, עד כדי כך שה-22 ביולי מכונה "יום קירוב פאי". לעומתו, ה-14 במרץ זכה לשם "יום פאי", אך האם הקירוב \(3.14\) אכן מדויק יותר מהקירוב \(\frac{22}{7}\)? למרבה הזוועה, התשובה היא שלילית, כך שיש לנו כאן אי צדק היסטורי. \(\frac{22}{7}=3.\overline{142857}\) (החלק שמעליו יש קו הוא החלק המחזורי), כך שהשגיאה שמקבלים היא \(\left|\pi-\frac{22}{7}\right|=0.0012644\dots\), בעוד שהשגיאה שמקבלים מהקירוב השני היא \(\left|\pi-3.14\right|=0.0015926\dots\). זה נהיה עוד יותר מרשים כאשר שמים לב לכך ש-\(3.14=\frac{314}{100}\), כלומר המכנה הוא 100, בעוד שהמכנה של \(\frac{22}{7}\) הוא קטן משמעותית.

בואו נעבור לקירוב הבא: \(\frac{333}{106}=3.1\overline{4150943396226}\). השגיאה כאן היא \(\left|\pi-\frac{333}{106}\right|=0.000083219\dots\) שהיא זעירה למדי: מסדר גודל של \(10^{-5}\). לעומת זאת אם היינו מבצעים קירוב עם המכנה \(100\) (כמו שעשינו קודם) היינו מקבלים שגיאה מסדר גודל של \(10^{-3}\) – גדולה פי מאה!

השורה התחתונה היא ששברים משולבים מספקים קירוב ריבועי, במובן הבא: אם \(\frac{A}{B}\) התקבל מתישהו בפיתוח של \(\alpha\) לשבר משולב, אז \(\left|\alpha-\frac{A}{B}\right|<\frac{1}{B^{2}}\): גודל השגיאה שלנו הוא ריבועי ביחס ל-\(B\), מה שאומר, נניח, שאם ל-\(B\) יש עשר ספרות, אז השגיאה היא מסדר גודל של עשרים ספרות אחרי הנקודה. זו רמת דיוק מרשימה ביותר, ומתברר שזה לא הכל – ניתן להוכיח כי הקירובים ששברים משולבים מספקים הם הטובים ביותר גם במובן הבא: אם \(\frac{A}{B}\) הוא קירוב שכזה, לא קיים קירוב יותר טוב לאותו מספר עם אותו ערך \(B\) במכנה.

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