מאה אנשים עומדים במעגל וממוספרים לפי סדר, מ-1 עד 100, בכיוון השעון.

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

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

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

שימו לב: ניחוש של "בערך באמצע" או "בסוף" לא יעבוד כאן. יש תשובה מדויקת אחת בלבד.

ואם פתרתם, נסו לענות גם על שאלת ההמשך: מהי הנוסחה הכללית עבור מעגל של n אנשים?

רמז דק

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

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

רמז עבה

אם תבדקו, תגלו שכאשר מספר האנשים הוא חזקה של שתיים - 2, 4, 8, 16, 32, 64 - השורד הוא תמיד מספר 1. הסיבה יפה: בכל סיבוב שלם בדיוק חצי מהאנשים יוצאים, המעגל נשאר חזקה של שתיים, והתור חוזר תמיד לאותו אדם.

עכשיו רשמו את מספר האנשים כחזקה של שתיים ועוד שארית: n שווה ל-2 בחזקת m ועוד L, כאשר 2 בחזקת m היא החזקה הגדולה ביותר שאינה עולה על n.

אחרי שיוצאים L אנשים, נותרים בדיוק 2 בחזקת m אנשים - ואז המצב "מתאפס". השאלה היחידה שנותרה היא מי מחזיק אז בתור.

פתרון

המקום הבטוח הוא מספר 73.

הנוסחה: רושמים את מספר האנשים בצורה n שווה ל-2 בחזקת m ועוד L, כאשר 2 בחזקת m היא החזקה הגדולה ביותר של שתיים שאינה עולה על n, ו-L הוא מה שנשאר. השורד הוא במקום 2L ועוד 1.

עבור מאה אנשים: החזקה הגדולה ביותר של שתיים שאינה עולה על 100 היא 64, ולכן L שווה 36. השורד הוא במקום 2 כפול 36 ועוד 1, כלומר 73.

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

בדיקה מהירה של הנוסחה על מספרים קטנים: עבור 5 אנשים מקבלים 4 ועוד 1, כלומר L שווה 1 והשורד הוא 3. עבור 10 אנשים מקבלים 8 ועוד 2, כלומר L שווה 2 והשורד הוא 5. נסו לעקוב ידנית ותיווכחו.

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