בעיית הנהגים הגחמנים

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

הבעיה

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

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

פונקציה, המתאימה את הנהגים למקומות החניה, כך שלכל נהג יש מקום חניה, קרויה פונקציית חניה. הדיון בפונקציות כאלה החל במאמר
A.G. Konheim, B. Weiss, An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966) 1266-1274.

דוגמה

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

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

פתרון הבעיה

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

סדרה $\ (a_{1},a_{2},a_{3},...,a_{n})$ של מספרים בתחום 1 עד n תקרא פונקציית חניה, אם כאשר לכל $\ 1\leq i\leq n$, הנהג ה-$\ i$ בוחר במקום החניה ה$\ a_{i}$ בתור מקום מועדף, כל הנהגים מוצאים חניה.

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

רשימה של העדפות (כמתואר מלמעלה) היא פונקציית חניה, אם ורק אם אף נהג אינו חונה במקום חניה ה$\ n+1$:

• אם אחד הנהגים עזב את החניון, מישהו יצטרך לחנות לאחר מקום החניה ה$\ n$, ולכן יחנה במקום החניה ה$\ n+1$ (כי הוא הראשון אחרי ה$\ n$).
• אם מישהו חונה במקום החניה ה$\ n+1$, זאת אומרת שמישהו הגיע למקום החניה ה$\ n$ והוא היה תפוס, ולכן היה אמור לעזוב את החניון, או שמישהו בחר במקום ה$\ n+1$, אבל בפונקציית חניה זה לא אפשרי (הרי $\ 1\leq a_{i}\leq n$).

נשים לב שהזזה ציקלית של הרשימה, מזיזה ציקלית את התוצאה הסופית של המעגל. כלומר, תהי $\ (b_{1},b_{2},b_{3},...,b_{n})$ רשימת העדפות של הנהגים. (כלומר, לכל $\ 1\leq i\leq n$ ,$\ 1\leq b_{i}\leq n+1$ הוא המקום חניה המועדף על הנהג ה$\ i$), ותהי $\ (p_{1},p_{2},p_{3},...,p_{n})$ רשימת הסיום במקרה זה (כלומר, בסוף התהליך סיים הנהג ה$\ i$, במקום ה$\ p_{i}$). אזי רשימת הסיום של רשימת ההעדפות $\ (b_{1}+j,b_{2}+j,b_{3}+j,...,b_{n}+j){\pmod {(n+1)}}$ היא $\ (p_{1}+j,p_{2}+j,p_{3}+j,...,p_{n}+j){\pmod {(n+1)}}$

כלומר, כל פונקציית חניה מופיעה ברשימות של ההעדפות האפשריות $\ n+1$ פעמים:

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

כעת נסתכל על מספר הרשימות של ההעדפות האפשריות עם מקום החניה הנוסף: ישנן $\ {(n+1)}^{n}$ כאלה (כי לכל נהג יש $\ n+1$ אפשרויות למקום מועדף, ויש $\ n$ נהגים.

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