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

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

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

על 4 אין פשרות!

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

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

“הגיעו היום 30 מועמדות שמתוכן אני צריכה לבחור, אז את 10 הראשונות אני דוחה בלי לחשוב בכלל, ומה-11 והלאה אני בודקת אם היא הטובה ביותר מבין כל אלו שהתראיינו עד כה, ואם כן - אני מקבלת אותה”.

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

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

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

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

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

אם כן, מהשהסכמנו שהכלל שמוביל לבחירת מזכירה הוא “היא הטובה ביותר מבין מי שראיינו עד כה”, נשאלת רק השאלה מתי להפעיל אותו. הרי ברור שיהיה מטופש להפעיל אותו כבר מהרגע הראשון - המזכירה הראשונה שאנחנו מראיינים היא הטובה ביותר מבין מי שראיינו עד כה, אבל אם המזכירות באות בסדר אקראי, ההסתברות שלנו לבחור במזכירה הטובה ביותר באופן הזה היא \( \frac{1}{n} \). בדוגמה של ה-30 מזכירות שלנו, זו הסתברות של \( \frac{1}{30} \), כלומר קצת פחות מ-4 אחוזים. אם יש 1000 מזכירות אז ההסתברות צונחת לה ל-0.1 אחוזים מביכים. ואנחנו אמרנו שבשיטה האופטימלית אפשר להצליח ב-37 אחוז מהפעמים בלי קשר בכלל למספר המזכירות - אני מקווה שאחוזי ההצלחה הללו (ובעיקר, האופן שבו הם לא תלויים בכלל במספר המזכירות) נראים כבר יותר מרשימים מאשר אולי נראו במבט ראשון.

אם כן, אנחנו רוצים לחכות קצת, לקבל מדגם כלשהו של מזכירות, לדחות אותן, והחל משלב מסויים להתחיל להפעיל את כלל “קבל את הטובה ביותר עד כה”. מספר השלבים הזה יכול להיות קבוע (“תוך 13 שלבים, בלי קשר למספר המזכירות”) ויכול להיות גם קשור איכשהו למספר המזכירות (“אחרי שבדיוק חצי מהמזכירות התראיינו”) ויכול גם להיות תלוי איכשהו בראיונות שכבר בוצעו; אבל הראיונות שכבר בוצעו תמיד מניבים את אותה התוצאה - אחרי \( k \) ראיונות יש לנו רשימה של \( k \) מזכירות שלא קיבלנו שאפשר לסדר מהגרועה לטובה ביותר. אין לנו מידע, למשל, על האיכות של אותן מזכירות ביחס לאלו שעוד לא ראיינו. לכן אם יש כלל לקביעת הנקודה שממנה והלאה מפעילים את כלל “קבל את הטובה ביותר עד כה” הוא לא יהיה תלוי בראיונות שבוצעו עד כה (זה קצת נפנוף ידיים; אפשר לתת לזה הוכחה מדויקת אבל קצת טרחנית).

אם כן, תוך כמה צעדים כדאי להתחיל להפעיל את הכלל? התוצאה המפתיעה (?) היא שמדובר על \( \frac{n}{e} \) צעדים, כאשר \( e=2.71828183\dots \) הוא בסיס הלוגריתם הטבעי - הקבוע המפורסם ביותר במתמטיקה חוץ מ-\( \pi \). אמרתי כבר בבלוג שאני אוהב את \( e \) יותר, והבעיה הזו היא דוגמה נוספת לסיבה לכך - \( e \) צץ במקומות עוד יותר מגוונים מאשר \( \pi \) לטעמי.

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

אז שוב, כדי שכולם יהיו איתי: עבור \( k \) טבעי כלשהו ו-\( n \) מזכירות, אנו בודקים מה ההסתברות לבחור את המזכירה הטובה ביותר אם את \( k-1 \) הראשונות אנו דוחים, ומקבלים את המזכירה הראשונה אחרי אותן \( k \) שהיא טובה יותר מכל מי שהיו עד כה (אם אין כזו, אכלנו אותה).

כאשר דיברתי בבלוג על הסתברות מותנית הזכרתי מושג שנקרא “נוסחת ההסתברות השלמה”. בואו נזכיר אותה: אם \( A \) הוא מאורע כלשהו - במקרה שלנו, “המזכירה הטובה ביותר נבחרה”, ואם \( B_{1},\dots,B_{n} \) היא סדרה של מאורעות זרים שמתארים את מרחב ההסתברות כולו - במקרה שלנו, \( B_{i} \) הוא המאורע “המזכירה ה-\( i \) מבין המרואיינות היא הטובה ביותר” - אז מתקיים \( P\left(A\right)=\sum_{i=1}^{n}P\left(A|B_{i}\right)P\left(B_{i}\right) \), כאשר \( P\left(A|B_{i}\right) \) מייצג את ההסתברות שהמזכירה הטובה ביותר נבחרה בהינתן שהמזכירה ה-\( i \) הייתה הטובה ביותר.

בפוסט ההוא אמרתי: “על פניו היא נראית כמו דרך מסובכת יותר לכתוב את \( P\left(A\right) \), אך כאמור – לעתים קרובות הדרך הנוחה ביותר לחשב את \( P\left(A\right) \) היא על ידי חלוקה למקרים שמיוצגים על ידי ה-\( B_{i} \)”. זו אכן דוגמה קלאסית לכך.

את \( P\left(B_{i}\right) \) קל לחשב; מה ההסתברות לכך שהמזכירה ה-\( i \) היא הטובה ביותר? זה קל - מכיוון שהסדר שבו המזכירות נכנסות נבחר באקראי ובהתפלגות אחידה מכל הסדרים האפשריים, כל מקום סביר באותה מידה עבור המזכירה הטובה ביותר, ולכן \( P\left(B_{i}\right)=\frac{1}{n} \).

ומהו \( P\left(A|B_{i}\right) \)? אם \( i\le k \) אז \( P\left(A|B_{i}\right)=0 \), על פי החוק שלנו של לדחות אוטומטית את \( k \) הראשונות (אם הטובה ביותר הייתה בין \( k \) הראשונות, אין שום סיכוי שנבחר את הטובה ביותר). החלק המעניין הוא כש-\( i>k \). במקרה זה \( P\left(A|B_{i}\right) \) הוא ההסתברות שנבחרה המזכירה במקום ה-\( i \), בהינתן שבמקום ה-\( i \) אכן נמצאת המזכירה הטובה ביותר. השאלה היא - איך ייתכן שהיא לא תיבחר? זה יקרה רק אם אחת מהמזכירות במקומות \( k,k+1,\dots,i-1 \) הצליחה להידחף איכשהו - כלומר הייתה טובה יותר מכל המזכירות שלפניה.

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

את ההסתברות של הקריטריון קל כעת לחשב - למזכירה הטובה ביותר יש \( i-1 \) מקומות אפשריים להיות בהם; כל מקום סביר באותה מידה; ולכן ההסתברות שהיא תהיה באחד מ-\( k \) המקומות הראשונים היא \( \frac{k}{i-1} \). לכן \( P\left(B_{i}\right)=\frac{k}{i-1} \). אם זה התקיים, אז למזכירה במקום ה-\( i \) לא היו הפרעות והיא נבחרה בודאות (הרי היא הטובה ביותר, ולכן בפרט הייתה טובה מכל המזכירות שלפניה).

נוסחת ההסתברות השלמה כעת נותנת לנו:

\( P\left(A\right)=\sum_{i=1}^{n}P\left(A|B_{i}\right)P\left(B_{i}\right)=\sum_{i=k+1}^{n}\frac{k}{i-1}\cdot\frac{1}{n}=\frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1} \).

יופי. עכשיו נתקענו. מה עושים עם הסכום \( \sum_{i=k+1}^{n}\frac{1}{i-1} \) המעצבן? כאן מסתיים החלק היחסית פשוט של הפוסט ואנו עוברים לחלק הטכני, שלטעמי הוא יפה ומעניין לא פחות, אבל אולי לא מיועד לבעלי לב חלש מתמטית.

ראשית, שימו לב לכך שהסכום שלעיל שווה ל-\( \sum_{i=k}^{n-1}\frac{1}{i} \) בבירור (ביצענו את החלפת המשתנה הפשוטה \( i\mapsto i+1 \)). לסכום הזה קשר הדוק לאחד הטורים החשובים במתמטיקה - הטור ההרמוני, \( \sum_{i=1}^{\infty}\frac{1}{i} \). כפי שכבר הראיתי בעבר בבלוג, הטור הזה מתבדר לאינסוף - ככל שסוכמים בו עוד ועוד איברים, התוצאה גדלה וגדלה באופן בלתי חסום ועוברת כל מספר טבעי בשלב מסויים (אף שיש טענות שהוא דווקא מתכנס ל-137). אבל, הבה ונדבר לרגע על הסכומים החלקיים של הטור, מה שמתקבל אחרי שסוכמים רק את \( n \) האיברים הראשונים מתוכו, כלומר \( H_{n}=\sum_{i=1}^{n}\frac{1}{i} \). ל-\( H_{n} \) קוראים המספר ההרמוני ה-\( n \)-י, ועליו המתמטיקאים יודעים לא מעט. שימו לב ש-\( \sum_{i=k}^{n-1}\frac{1}{i}=H_{n-1}-H_{k-1} \), ולכן השאלה שאנחנו רוצים לפתור היא בעצם זו: מהו \( \lim_{n\to\infty}\frac{k}{n}\left(H_{n-1}-H_{k-1}\right) \)?

כאן כדאי לשלוף את מה שידוע על המספרים ההרמוניים. למרבה המזל, אנחנו יודעים לקרב אותם מצויין בעזרת פונקציה שאנחנו מכירים היטב - הלוגריתם הטבעי, \( \ln n \). למעשה, הסדרה ההרמונית \( H_{n} \) היא מעין אנלוג בדיד של \( \ln n \); זאת מכיוון ש-\( H_{n}=\sum_{i=1}^{n}\frac{1}{i} \) ואילו \( \ln n=\int_{1}^{n}\frac{1}{x}dx \). ניתן להוכיח, ואראה זאת בקרוב, ש-\( \lim_{n\to\infty}\left(H_{n}-\ln n\right)=\gamma \) כאשר \( \gamma \) הוא מספר קבוע (קטן למדי, אבל זה לא חשוב לנו) המכונה “קבוע אוילר-מסקרוני” וערכו הוא בערך \( \gamma=0.5772\dots \). ואני אומר “בערך” כי המספר הזה הוא עדיין תעלומה לא קטנה - עדיין לא ידוע אפילו אם הוא רציונלי או אי רציונלי.

דרך אחרת, אולי קצת יותר נוחה, לתאר את הגבול למעלה היא זו: \( H_{n}=\ln n+\gamma+o\left(1\right) \). מילולית, זה אומר “המספר ההרמוני ה-\( n \)-י הוא \( \ln n \) ועוד קבוע אוילר-מסקרוני, ועוד משהו שאני לא יודע איך הוא נראה אבל כש-\( n \) שואף לאינסוף הוא שואף לאפס” (המשמעות הפורמלית של \( o\left(1\right) \) היא זו: פונקציה \( f\left(n\right) \) היא \( o\left(1\right) \) - או-קטן של \( 1 \) - אם \( \frac{f\left(n\right)}{n}\to0 \)).

כעת, מהו \( H_{n-1}-H_{k-1} \)? עם הקירוב שתיארתי זה פשוט:

\( H_{n-1}-H_{k-1}=\left(\ln\left(n-1\right)+\gamma+o\left(1\right)\right)-\left(\ln\left(k-1\right)+\gamma+o\left(1\right)\right)=\ln\left(\frac{n-1}{k-1}\right)+o\left(1\right) \)

המעבר האחרון נובע מזהות סטנדרטית בלוגריתמים: \( \ln a-\ln b=\ln\left(\frac{a}{b}\right) \) (הרבה מהכוח של לוגריתמים נובע מכך שחיבור וחיסור שלהם מתאימים לכפל וחילוק מספרים).

אני משער שמדגדג לכם בשלב זה להיפטר מהמינוסים המעצבנים שדבוקים ל-\( n \) ו-\( k \). ובכן, שימו לב לכך ש-\( H_{n-1}-H_{n}=\ln\left(\frac{n-1}{n}\right)+o\left(1\right)=\ln\left(1-\frac{1}{n}\right)+o\left(1\right)=o\left(1\right) \), כשהמעבר האחרון נובע מכך ש-\( \lim_{n\to\infty}\ln\left(1-\frac{1}{n}\right)=\ln\left(1\right)=0 \). דרך מסובכת להגיד פורמלית את הרעיון הטריוויאלי ש-\( H_{n} \) ו-\( H_{n-1} \) הם אותו הדבר לכל צורך מעשי כאשר \( n \) שואף לאינסוף, ולכן אפשר להחליף ביניהם. למי שהפורמליות עדיין חשובה לו, הנה הטריק במלואו:

\( H_{n-1}-H_{k-1}=\left(H_{n-1}-H_{n}+H_{n}\right)-\left(H_{k-1}-H_{k}+H_{k}\right)=H_{n}-H_{k}+o\left(1\right)=\ln\left(\frac{n}{k}\right)+o\left(1\right) \)

אם כן, חזרה לעניינו המקורי - צמצמנו את בעיית המזכירה לגבול \( \lim_{n\to\infty}\frac{k}{n}\ln\left(\frac{n}{k}\right) \). כפי שאפשר לנחש, המפתח לתעלומה הוא היחס \( \frac{k}{n} \). צריך לזכור ש-\( k \) אינו קבוע בהכרח, אלא הוא פונקציה כלשהי של \( n \), ואנחנו רוצים לדעת איזו פונקציה מניבה לנו את הערך המקסימלי - את הסתברות ההצלחה המקסימלית לבחור במזכירה הטובה ביותר. לשם כך, הבה ונסמן \( x=\frac{k}{n} \), וכעת עלינו לחקור את הפונקציה \( x\ln\left(\frac{1}{x}\right)=-x\ln x \) עבור הערכים \( 0<x\le1 \). ב”חקירה” אני מתכוון ל”להבין איפה יש לפונקציה מקסימום אם בכלל”

הדרך הסטנדרטית לבצע חקירה שכזו היא באמצעות נגזרות. קל לחשב את הנגזרת של הפונקציה הזו - היא \( -\ln x-x\cdot\frac{1}{x}=\ln\left(\frac{1}{x}\right)-1 \). על כן, הנגזרת מתאפסת כאשר \( \ln\left(\frac{1}{x}\right)=1 \), כלומר \( \frac{1}{x}=e \), כלומר \( x=\frac{1}{e} \) - הנה המספר הזה צץ סוף סוף. האם ההתאפסות הזו היא נקודת מינימום או מקסימום של הפונקציה? ובכן, אם תחקרו קצת בעצמכם תגלו שהנגזרת היא פונקציה יורדת, שבהתחלה היא חיובית ואחר כך שלילית. כלומר, הפונקציה המקורית קודם עולה, ואז יורדת - מה שאומר ש-\( x=\frac{1}{e} \) היא נקודת המקסימום. המסקנה: אם אנחנו רוצים למקסם את הסיכוי שלנו לבחור את המזכירה הטובה ביותר, אנחנו רוצים תמיד לבחור \( k \) כך ש-\( \frac{k}{n}=\frac{1}{e} \), כלומר \( k=\frac{n}{e} \). מכיוון ש-\( e \) הוא אי רציונלי לעולם לא נוכל לבחור \( k \) שיקיים את השוויון הזה בדיוק; אבל מכיוון ש-\( x\ln\left(\frac{1}{x}\right) \) היא פונקציה רציפה, ככל שנבחר \( k \) שקרוב יותר ל-\( \frac{n}{e} \) נקבל סיכוי הצלחה גבוה יותר.

זה סוף בעיית המזכירה, אבל נשאר לנו להבין איך מוכיחים את ההערכה על גודל המספרים ההרמוניים, \( H_{n}=\ln n+\gamma+o\left(1\right) \). לשם כך נכניס לתמונה מושג חדש - פונקצית הזטא של רימן. עבור \( s>1 \) ממשי, פונקצית הזטא של רימן מוגדרת כ-\( \zeta\left(s\right)=\sum_{n=1}^{\infty}\frac{1}{n^{s}} \) (תיארתי בפירוט רב יותר את הפונקציה והקשר שלה להשערת רימן בעבר). למשל, \( \zeta\left(2\right)=\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6} \) (איך מוכיחים את השוויון הזה? גם את זה הראיתי בעבר). בנוסף, נכליל את המספרים ההרמוניים באופן טבעי כדי שיתארו את העניין הזה: \( H_{n}^{\left(s\right)}=\sum_{i=1}^{n}\frac{1}{i^{s}} \).

לב ההוכחה הוא נעוץ בהיכרות הטובה שלנו עם \( \ln n \). אנחנו יודעים לתאר את \( \ln n \) כטור אינסופי: הנוסחה המפורסמת ביותר (שאותה לא אוכיח כאן, יש גבול…) היא \( \ln\left(\frac{1}{1-x}\right)=\sum_{n=1}^{\infty}\frac{x^{n}}{n} \) שתקפה כאשר \( -1\le x<1 \). ניקח \( k>1 \) טבעי כלשהו וננסה להשתמש בנוסחה כדי לתאר כטור את \( \ln\left(\frac{k}{k-1}\right) \): מכיוון ש-\( \frac{k}{k-1}=\frac{1}{1-1/k} \), נקבל ש-\( \ln\left(\frac{k}{k-1}\right)=\sum_{n=1}^{\infty}\frac{1}{nk^{n}} \). הטור הזה נראה קצת יותר נחמד כשכותבים אותו במפורש: \( \ln\left(\frac{k}{k-1}\right)=\frac{1}{k}+\frac{1}{2k^{2}}+\frac{1}{3k^{3}}+\dots \).

כעת הבה ונקבע \( n \) כלשהו, ונסכום את \( \ln\left(\frac{k}{k-1}\right) \) לכל \( 1<k\le n \). בזכות התכונה של הפיכת-חיבור-לכפל של לוגריתמים, התוצאה תהיה שרשרת יפה של ביטולים:

\( \ln\left(\frac{n}{n-1}\right)+\ln\left(\frac{n-1}{n-2}\right)+\dots+\ln\left(\frac{3}{2}\right)+\ln\left(\frac{2}{1}\right)=\ln\left(\frac{n}{n-1}\cdot\frac{n-1}{n-2}\cdots\frac{3}{2}\cdot\frac{2}{1}\right)=\ln n \)

מה זה עזר לנו? שכעת אפשר לכתוב את \( \ln n \) כסכום של טורים:

\( \ln n=\sum_{k=2}^{n}\left(\frac{1}{k}+\frac{1}{2k^{2}}+\frac{1}{3k^{3}}+\dots\right) \)

כל טור שכזה מתכנס, והוא חיובי, ולכן ניתן לשנות את סדר האיברים בסכימה בלי חשש מעיוותים כמו זה של משפט רימן. אם כן, מה קיבלנו? ש-\( \ln n=\sum_{k=2}^{n}\frac{1}{k}+\frac{1}{2}\sum_{k=2}^{n}\frac{1}{k^{2}}+\frac{1}{3}\sum_{k=2}^{n}\frac{1}{k^{3}}+\dots \)

כעת שימו לב ש-\( \sum_{k=2}^{n}\frac{1}{k}=H_{n}-1 \) (כי האיבר הראשון בטור, עבור \( k=1 \), חסר). בדומה, \( \sum_{k=2}^{n}\frac{1}{k^{s}}=H_{n}^{\left(s\right)}-1 \). לכן קיבלנו:

\( \ln n=\left(H_{n}-1\right)+\frac{1}{2}\left(H_{n}^{\left(2\right)}-1\right)+\frac{1}{3}\left(H_{n}^{\left(3\right)}-1\right)+\dots \)

ולכן העברת אגפים זריזה נותנת לנו ש:

\( H_{n}-\ln n=1-\frac{1}{2}\left(H_{n}^{\left(2\right)}-1\right)-\frac{1}{3}\left(H_{n}^{\left(3\right)}-1\right)+\dots \)

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

\( \lim_{n\to\infty}\left(H_{n}-\ln n\right)=1-\frac{1}{2}\left(\zeta\left(2\right)-1\right)-\frac{1}{3}\left(\zeta\left(3\right)-1\right)-\dots \)

והנה קיבלנו ייצוג נאה של \( \gamma \): \( \gamma=1-\frac{1}{2}\left(\zeta\left(2\right)-1\right)-\frac{1}{3}\left(\zeta\left(3\right)-1\right)-\dots \). הספקנים שבכם אולי יתהו למה הטור הזה מתכנס בכלל; לשם כך מספיק להראות שהטור החיובי \( \sum_{k=2}^{\infty}\left(\zeta\left(k\right)-1\right) \) מתכנס, ואותו אפשר לכתוב כ-\( \sum_{k=2}^{\infty}\sum_{n=2}^{\infty}\frac{1}{n^{k}} \), להחליף את סדר הסכימה כדי לקבל סכום של טורים גאומטריים \( \sum_{n=2}^{\infty}\left(\sum_{k=2}^{\infty}\frac{1}{n^{k}}\right)=\sum_{n=2}^{\infty}\frac{1}{n\left(n-1\right)} \) והטור הזה כבר בבירור מתכנס על ידי מבחן השוואה סטנדרטי (המעבר האחרון הוא פשוט שימוש מהיר בנוסחה לטורים גאומטריים אינסופיים).

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