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

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

הבעיה

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

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

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

דוגמה

נניח שהנהג הראשון מעדיף את המקום 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}$ רשימות העדפות, המאפשרות לכולם לחנות לפי הכללים.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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