בעיית יוספוס

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

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

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

הנוסח הכללי של בעיה זו הוא: n אנשים עומדים במעגל, ונתון מספר טבעי m < n. מתחילים עם אדם כלשהו במעגל, ומוציאים מהמעגל כל אדם m. תהליך זה נמשך עד להשארת k אנשים. כאשר k=1 (כלומר התהליך נמשך עד שנותר אדם אחד בלבד) סדר ההוצאות של האנשים נותן את תמורת יוספוס (Josephus permutation), ויש לחשב תמורה זו. דוגמה: במעגל שבעה אנשים, ומוציאים כל אדם שלישי. סדר ההוצאה הוא, משמאל לימין: {3,6,2,7,5,1,4}.

הבעיה התגלגלה גם לפתחם של העוסקים במדעי המחשב, כדוגמה לאלגוריתם, והם קבעו שלפתרונה סיבוכיות זמן (O(n²

לקריאה נוספת

• W.W. Rouse Ball and H.S.M Coxeter, Mathematical Recreations and Essays

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

• בעיית יוספוס, באתר MathWorld (באנגלית)

• Alexander Bogomolny, Josephus Flavius game, in Cut-the-Knot site.
• Josephus' Problem

• בעיית יוספוס: כך תהיה השורד האחרון, באתר ynet, 17 בנובמבר 2016