בעיית המזכירה

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

עקרונות הבעיה

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

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

הפתרון האופטימלי לבעיה מתאפיין בכך שעבור ערכים גדולים של $N$, ההסתברות לבחור במועמדת הטובה ביותר היא קצת יותר משליש, או ליתר דיוק היא קרובה ל-${\frac {1}{e}}$ או אחד חלקי הקבוע ℮ ששווה בערך 2.71828. תוצאה זו נחשבת כמפתיעה, בגלל שממבט ראשון קשה להאמין שמתוך 100 מועמדות, ההסתברות שנצליח לבחור את המועמדת הטובה ביותר תהיה כל כך גבוהה, בפרט שבחירה אקראית (למשל, אם תמיד נשכור את המועמדת החמישית שנראיין, תהיה אשר תהיה) תבחר במועמדת הטובה ביותר רק פעם אחת למאה.

ההיסטוריה של הבעיה

בקרב מתמטיקאים, הבעיה הייתה ידועה מתחילת שנות ה-1950, אך הבעיה והפתרון לא נכתבו או פורסמו. בפעם הראשונה שהבעיה הוזכרה בכתב הייתה בטור של מרטין גרדנר מפברואר 1960 בבטאון Scientific American. כפי שגרדנר ניסח את הבעיה, היא בעצם אינה באופן מדויק זהה לבעיית המזכירה, אך הוא התעלם מההבדלים בפתרונו והתייחס אליה כבעיית המזכירה כפי שהיא ידועה כיום (ראו הסבר מפורט למטה). הפתרון לבעיה פורסם חודש לאחר מכן, ויוחס למתמטיקאים מוזר ופאונדר. ב-1963 הציבו זוג מתמטיקאים, ב. ביסינג'ר וקונרד סיגל, את אותה הבעיה בכתב-העת המתמטי The American Mathematical Monthly כאתגר לפותרים, וכעבור כמה חודשים פורסם הפתרון, עם הערה שגם הבעיה וגם הפתרון כבר פורסמו ב-Scientific American מספר שנים קודם.

ניסוח הבעיה

ישנן $N$ מועמדות למשרה, מספר שידוע מראש.

את המועמדות אפשר לדרג מ-1 עד $N$ לפי המוסכמה שדרוג יותר גבוה ניתן למועמדת מועדפת (כלומר המועמדת המועדפת ביותר תדורג כ-$N$).

מכיוון שישנן $N$ מועמדות, מספר האפשרויות שאפשר לסדר אותן בתור הוא

$\ N!=N\times (N-1)\times (N-2)\times ...\times 3\times 2\times 1$

כדוגמה, כש-$N$ שווה ל-3, ישנן 6 אפשרויות לסדר את שלוש המועמדות (שמסודרות מימין לשמאל):

$3\leftarrow 2\leftarrow 1$

$2\leftarrow 3\leftarrow 1$

$3\leftarrow 1\leftarrow 2$

$1\leftarrow 3\leftarrow 2$

$2\leftarrow 1\leftarrow 3$

$1\leftarrow 2\leftarrow 3$

ההנחה היא שהסדר בו המועמדות יופיעו נבחר באופן אחיד מבין כל $!N$ הדרכים שניתן לסדר אותן.

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

$3\leftarrow 2\leftarrow 1$

$2\leftarrow 3\leftarrow 1$

$1\leftarrow 3\leftarrow 2$

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

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

הפתרון האופטימלי

כאמור, מספר המועמדות עליו כדאי לפסוח תלוי ב-$N$. אבל אפשר להראות שעבור $N$ גדול דיו, מספר המועמדות שעליו כדאי לוותר שואף ל-${\frac {N}{e}}$ . במילים אחרות, עבור מספר גדול של מועמדות, האסטרטגיה האופטימלית היא לפסוח על אחוז קבוע מהמועמדות (בערך 37%) ואז לבחור את המועמדת הראשונה שניקרית שמועדפת על הטובה מבין המועמדות הראשונות הללו.

כפי שכבר הוזכר לעיל, תחת אסטרטגיה זו, ההסתברות שנבחר נכון היא בערך ${\frac {1}{e}}$, קרוב שיהיה יותר מדיוק ככל ש-$N$ יותר גדול.

הסבר לפתרון

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

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

$2\leftarrow 3\leftarrow 1$

$3\leftarrow 1\leftarrow 2$

$1\leftarrow 3\leftarrow 2$

ובמקרים האלו, השיטה תכשל:

$3\leftarrow 2\leftarrow 1$

$2\leftarrow 1\leftarrow 3$

$1\leftarrow 2\leftarrow 3$

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

משחק גוגול

כשלראשונה העלה לכתב מרטין גרדנר את הבעיה, לה קרא "משחק גוגול", הוא ניסח אותה באופן קצת שונה מכפי שתוארה לעיל (וביסינג'ר וסיגל ניסחו את הבעיה באותה צורה כמוהו כשהציבו אותה ב-American Mathematical Monthly). ההבדל מצביע על החשיבות בניסוח בעיה כזו באופן מדויק. בפרט, גרדנר תיאר מצב בו אדם כותב מספרים שונים על $N$ פיסות נייר, זורק את כולן לכובע, ושולף אותן בסדר אקראי. הוא שאל כיצד ניתן להגדיל את ההסתברות שנבחר במספר הגבוה ביותר מבין כל הפתקים.

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

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

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

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

הכללות של בעיית המזכירה

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

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

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

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

לקריאה נוספת

• T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296, 1989.

קישורים חיצוניים

• גדי אלכסנדרוביץ', בעיית המזכירה, ואיך זה קשור למספרים הרמוניים, באתר "לא מדויק",