צילום: Marionaaragay, Wikimedia Commons (CC BY-SA 3.0)

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

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

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

ארבעים ואחד אנשים עומדים במעגל, ממוספרים 1 עד 41 בכיוון השעון. מתחילים לספור מאדם מספר 1, וכל אדם שלישי יוצא מהמעגל. כלומר: 3 יוצא, 6 יוצא, 9 יוצא, וכן הלאה.

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

השאלה: באיזה מקום במעגל צריך לעמוד כדי להיות האחרון שנשאר? ואם רוצים להישאר שניים - היכן עומד השני?

רמז דק

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

רמז עבה

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

לכן אם נסמן ב-J(n) את מקומו של הניצול במעגל של n אנשים, מתקיים הקשר:

J(1) = 0, ולכל n גדול מ-1: J(n) = (J(n-1) + 3) מודולו n.

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

פתרון

התשובה: הניצול היחיד עומד במקום 31. אם משאירים שניים, הם עומדים במקומות 16 ו-31.

איך מגיעים לזה?

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

J(1)=0, J(2)=1, J(3)=1, J(4)=0, J(5)=3, J(6)=0, J(7)=3, J(8)=6, J(9)=0, J(10)=3

וממשיכים באותה דרך עד:

J(40)=27, ולבסוף J(41) = (27+3) מודולו 41 = 30.

המקומות ממוספרים מאפס, ולכן המקום האמיתי הוא 30+1 = 31.

ריצה דומה על "שני הניצולים האחרונים" נותנת את הזוג 16 ו-31.

ומה עם יוספוס?

כאן נמצא העוקץ ההיסטורי של הסיפור. לפי המסורת המתמטית, יוספוס - שהיה איש משכיל ומהיר חשבון - חישב במהירות היכן ייפול המקום האחרון, והציב את עצמו ואת חברו בדיוק במקומות 31 ו-16. השניים נותרו לבדם, ויוספוס נכנע לרומאים, שרד, ועוד כתב את "תולדות מלחמת היהודים ברומאים" - הספר שבזכותו אנחנו בכלל מכירים את הסיפור.

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