בעיית יוספוס

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

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

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

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

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

פתרון ב #c

static int Josephusproblem(int n, int m)

{

if (n ==1){

return 1;

}

return (Josephusproblem( n-1, m)+m-1) % (n)+1;

}

לקריאה נוספת

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

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

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

בעיית יוספוס, סרטון באתר יוטיוב

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