בעיית 100 האסירים

הבנת הבעיה

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

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

תנאי הניצחון: כל 100 האסירים חייבים למצוא את המספר שלהם. אם אפילו אחד נכשל — כולם נכשלים.

אסטרטגיה אקראית

(1/2)^100

פחות מ-1 לטריליון
בלתי אפשרי למעשה

אסטרטגיית השרשרת

≈ 31.18%

1 − ln(2) ≈ 0.3118
הסיכוי מפתיע לטובה!

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

תובנת המפתח: סידור הפתקים מגדיר פרמוטציה מתמטית. כל פרמוטציה מתפרקת למחזורים (cycles) נפרדים. האסטרטגיה מצליחה אם ורק אם אף מחזור אינו ארוך מ-50.

נסו לצעוד בעצמכם בדמו הבא כדי לראות איך השרשרת עובדת:

DEMO — 10 קופסאות · אסיר #0 עוקב אחרי השרשרת

לחצו ▶ צעד כדי להתחיל

למה זה עובד? כל האסירים עוקבים אחרי שרשראות מאותה פרמוטציה — הגורלות שלהם תלויים זה בזה. ההסתברות שאף מחזור לא יעלה על 50 שווה בדיוק 1 − ln(2) ≈ 31.18%.

🔢 מאיפה מגיע 31.18%? — ההסבר המתמטי

שאלה: מה ההסתברות שבפרמוטציה אקראית של n איברים, אף מחזור לא יהיה ארוך מ-n/2?

שלב 1 — חישוב ההסתברות הכישלון:
נשאל: מה ההסתברות שקיים מחזור באורך k > n/2?
בפרמוטציה של n איברים, יכול להיות לכל היותר מחזור אחד כזה (כי שניים כבר יחד יעלו על n).
ניתן להוכיח שההסתברות לקיום מחזור באורך בדיוק k שווה:

          P(cycle of length k) = 1/k
        

שלב 2 — חיבור כל הכישלונות:
מאחר שאלו אירועים זרים (לא יכולים להתרחש בו-זמנית), ההסתברות לכישלון היא:

          P(fail) = ∑(k = n/2+1 to n) 1/k

                  = 1/(n/2+1) + 1/(n/2+2) + ... + 1/n

שלב 3 — קירוב לוגריתמי:
הסכום הזה מזכיר את הגדרת האינטגרל. עבור n גדול:

          P(fail) ≈ ∫(n/2 to n) 1/x dx = ln(n) − ln(n/2) = ln(2) ≈ 0.6931
        

שלב 4 — ההסתברות להצלחה:

          P(success) = 1 − ln(2) ≈ 1 − 0.6931 = 0.3069
        

מדוע 0.3118 ולא 0.3069?
הקירוב האינטגרלי מניח n→∞. עבור n = 100 בדיוק, חישוב מדויק של הסכום נותן:

          P(fail, n=100) = 1/51 + 1/52 + ... + 1/100 ≈ 0.6882

          P(success, n=100) = 1 − 0.6882 ≈ 0.3118

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

סימולציה ויזואלית — צפו באסטרטגיה

לפני כתיבת קוד, הקדישו כמה דקות לצפייה בסימולציה. שימו לב כיצד צבעי הקופסאות חושפים את מבנה המחזורים — גוונים קרים (כחול/ציאן) למחזורים בטוחים ≤ 50, גוונים חמים (אדום/כתום) למחזורים מסוכנים. ניתן לדעת אם הסיבוב יצליח עוד לפני שאסיר אחד נכנס.

לחצו לטעינת הסימולציה האינטראקטיבית

טיפ: בחרו N = 10 (שמאל למעלה) כדי לראות את השרשראות בבירור. אחר כך עברו ל-N = 100 ולחצו ⚡ INSTANT לעשרות סיבובים — צפו כיצד שיעור ההצלחה מתכנס לכ-31.18%.

כתיבת הקוד — שלב אחרי שלב

שפה: Java | ללא ספריות חיצוניות — מערכים ולולאות בלבד.
הקוד מאורגן כמחלקה (class) בשם PrisonersProblem וקובץ App.java נפרד עם main.

מבנה המחלקה — PrisonersProblem.java

המחלקה מכילה שתי תכונות (fields) פרטיות, פעולה בונה אחת, ושלוש פעולות שתממשו:

public class PrisonersProblem {

    // ── תכונות המחלקה ──────────────────────────────────────
    private int   prisonersNumber;   // מספר האסירים / גודל המערך
    private int[] boxes;            // מערך הקופסאות (הפרמוטציה)

    // ── פעולה בונה ─────────────────────────────────────────
    public PrisonersProblem(int prisonersNumber) { /* TASK 0 */ }

    // ── פעולות ─────────────────────────────────────────────
    public void    generateUniqueRandomArray()               { /* PROVIDED */ }
    public int     serialSearchByValueChain(int startIndex)  { /* TASK 1  */ }
    public boolean testSerialSearchByValueChain()             { /* TASK 2  */ }
}

שימו לב: הפעולות אינן מקבלות את המערך כפרמטר — הן עובדות ישירות על this.boxes ועל this.prisonersNumber.

TASK 0 Constructor — PrisonersProblem(int prisonersNumber) ▶

הפעולה הבונה (constructor) נקראת אוטומטית כשיוצרים עצם חדש. תפקידה לאתחל את התכונות של העצם.

רמז: הפעולה הבונה מקבלת את prisonersNumber כפרמטר. שמרו אותו ב-this.prisonersNumber, ואתחלו את this.boxes כמערך ריק בגודל המתאים.

public PrisonersProblem(int prisonersNumber) {
    // TODO: שמרו את prisonersNumber בתכונה המתאימה

    // TODO: צרו מערך int[] חדש בגודל prisonersNumber ושמרו ב-this.boxes
}

ב-Java, this.boxes = new int[prisonersNumber] יוצר מערך ומאתחל את כל תאיו ל-0.
לאחר קריאה לפעולה הבונה, ה-boxes עדיין ריק — הוא ימולא על-ידי generateUniqueRandomArray().

PROVIDED generateUniqueRandomArray() ▼

פעולה זו ניתנת לכם מוכנה. היא מעדכנת את this.boxes בפרמוטציה אקראית של המספרים 0 עד prisonersNumber−1 בשיטת Fisher-Yates — O(n), התפלגות אחידה.

public void generateUniqueRandomArray() {
    for (int i = 0; i < this.prisonersNumber; i++)
        this.boxes[i] = i;

    Random rand = new Random();
    for (int i = this.prisonersNumber - 1; i > 0; i--) {
        int j    = rand.nextInt(i + 1);
        int tmp  = this.boxes[i];
        this.boxes[i] = this.boxes[j];
        this.boxes[j] = tmp;
    }
}

TASK 1 serialSearchByValueChain(int startIndex) ▶

זה לב האסטרטגיה. האסיר מתחיל בקופסה startIndex, קורא את הערך מתוך this.boxes, קופץ לאותו אינדקס, וממשיך בשרשרת. ספרו כל קופסה שנפתחה.

החזירו את מספר הקופסאות שנפתחו עד מציאת המספר. החזירו -1 אם מתגלה לולאה אינסופית.

רמז: השתמשו ב-this.boxes[currentIndex] (לא arr[...]). תנאי המציאה: this.boxes[currentIndex] == startIndex. השתמשו ב-boolean[] בגודל this.boxes.length כמגן מפני לולאות.

public int serialSearchByValueChain(int startIndex) {

    if (startIndex < 0 || startIndex >= this.boxes.length)
        throw new IllegalArgumentException("startIndex out of bounds");

    // TODO: הכריזו על boolean[] בגודל this.boxes.length

    int currentIndex = startIndex;
    int searchCount  = 0;

    while (true) {
        // TODO: הגדילו את searchCount ב-1

        // TODO: אם currentIndex כבר בוקר — החזירו -1

        // TODO: סמנו את currentIndex כמבוקר

        // TODO: אם this.boxes[currentIndex] == startIndex — החזירו searchCount

        // TODO: אחרת — currentIndex = this.boxes[currentIndex]
    }
}

ההבדל מהגרסה הפרוצדורלית: במקום arr[i] כותבים this.boxes[i].
מערך boolean[] מחליף HashSet — בדיקה ב-O(1) ללא ייבוא ספריות.

TASK 2 testSerialSearchByValueChain() ▶

פעולה זו מדמה סיבוב אחד שלם: קוראת ל-generateUniqueRandomArray() כדי לערבב מחדש את this.boxes, ואז בודקת שכל prisonersNumber האסירים הצליחו בתוך prisonersNumber/2 צעדים.

רמז: לא צריך ליצור מערך חדש — פשוט קראו ל-this.generateUniqueRandomArray(). לאחר מכן עברו בלולאה על כל startIndex מ-0 עד this.prisonersNumber - 1 וקראו ל-this.serialSearchByValueChain(startIndex).

public boolean testSerialSearchByValueChain() {

    // TODO: קראו ל-this.generateUniqueRandomArray() לערבוב הקופסאות

    // TODO: עברו בלולאה על כל האסירים (startIndex = 0 עד prisonersNumber-1)
    for ( /* TODO */ ) {

        // TODO: קראו ל-this.serialSearchByValueChain(startIndex)

        // TODO: אם התוצאה == -1 או גדולה מ-prisonersNumber/2 — החזירו false
    }

    return true; // כולם הצליחו
}

השתמשו ב-this.prisonersNumber / 2.0 כדי להימנע מבעיית חלוקה שלמה.
יציאה מוקדמת עם return false — נכונה ויעילה.

TASK 3 main(String[] args) — App.java ▶

בקובץ App.java נפרד: צרו עצם אחד מהמחלקה, והריצו עליו tests סיבובים. הפלט צריך להתכנס לכ-31.18%.

public class App {
    public static void main(String[] args) {

        int free  = 0;
        int tests = 10000;

        // TODO: צרו עצם PrisonersProblem עם 100 אסירים
        PrisonersProblem prisonersObj = /* TODO: new PrisonersProblem(100) */;

        // TODO: לולאה של tests פעמים
        for ( /* TODO */ ) {

            // TODO: קראו ל-prisonersObj.testSerialSearchByValueChain()
            // TODO: אם מחזירה true — הגדילו את free ב-1
        }

        System.out.println(100.0 * free / tests + "% of trials result in free prisoners.");
    }
}

שימו לב: יוצרים עצם אחד בלבד מחוץ ללולאה — כל הרצה משתמשת באותו עצם ורק מערבבת מחדש את boxes.
פלט צפוי: ≈ 31.18% — יהיו שינויים קטנים בין הרצות בגלל האקראיות.

בדקו את הקוד שלכם ויזואלית

בודק ויזואלי — JavaScript

ללא צורך ב-API

📋 איך להמיר את קוד ה-Java ל-JavaScript? (לחצו לפתיחה)

ההמרה מכנית לחלוטין — כמעט שורה-אחר-שורה:

Java	JavaScript
`this.boxes[i]`	`arr[i]`
`this.boxes.length`	`arr.length`
`boolean[] visited = new boolean[n]`	`let visitedFlags = new Array(arr.length).fill(false)`
`int x = 0;`	`let x = 0;`
`return searchCount;` (הצלחה)	`return { visited: chain, success: true };`
`return -1;` (כישלון)	`return { visited: chain, success: false };`

שימו לב: chain הוא מערך שמכיל את כל האינדקסים שנפתחו בסדר, הוסיפו לו chain.push(currentIndex) בכל צעד.

קוד JavaScript — מלאו את הלוגיקה שלכם

function customSearch(arr, startIndex) {
  // arr         = מערך הקופסאות  (במקום this.boxes)
  // startIndex  = מספר האסיר
  // החזירו: { visited: [אינדקסים שנפתחו לפי הסדר], success: true/false }

const half = Math.floor(arr.length / 2);      // במקום this.prisonersNumber / 2
  const visitedFlags = new Array(arr.length).fill(false);
  const chain = [];                              // חדש: תיעוד לויזואליזציה

let currentIndex = startIndex;
  let currentValue = arr[currentIndex];          // במקום this.boxes[currentIndex]
  let searchCount = 0;

while (currentValue !== startIndex && searchCount <= half) {

if (currentIndex < 0 || currentIndex >= arr.length)
      return { visited: chain, success: false }; // במקום: return -1

if (visitedFlags[currentIndex])
      return { visited: chain, success: false }; // במקום: return -1

chain.push(currentIndex);                    // חדש: תיעוד כל קופסה
    visitedFlags[currentIndex] = true;
    currentValue = arr[currentIndex];            // במקום this.boxes[currentIndex]
    currentIndex = currentValue;
    searchCount++;
  }

chain.push(currentIndex);                      // חדש: הקופסה האחרונה
  const success = (currentValue === startIndex) && (searchCount <= half);
  return { visited: chain, success };            // במקום: return searchCount
}

פועל עם: אלגוריתם ברירת מחדל

שאלות הרהור

שם מלא

כיתה

כתובת מייל

שאלה 1

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

הבעיה עם אסטרטגיה אקראית: אם כל אסיר בוחר 50 קופסאות באקראי, הסיכוי שלו להצליח הוא בדיוק 50%. אבל הגורלות של האסירים השונים בלתי תלויים זה בזה — כל אחד מטיל מטבע משלו. לכן ההסתברות שכולם יצליחו היא (½)¹⁰⁰ ≈ 0.

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

שאלה 2

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

מה זה מחזור: כל פרמוטציה מתפרקת למחזורים (cycles) נפרדים. מחזור הוא קבוצת קופסאות שמובילות זו לזו ואז חוזרות לנקודת ההתחלה. לדוגמה: קופסה 3 מכילה 7, קופסה 7 מכילה 1, קופסה 1 מכילה 3 — מחזור באורך 3.

הקשר לאסטרטגיה: אסיר מספר k עוקב תמיד בדיוק על המחזור שמכיל את k. אורך המחזור הזה קובע כמה צעדים ייקחו לו — הוא יצליח אם ורק אם אורך המחזור ≤ 50.

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

שאלה 3

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

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

מהיכן מגיע 31.18%: ניתן לחשב מתמטית שההסתברות שפרמוטציה אקראית של n איברים לא תכיל מחזור ארוך מ-n/2 שווה בקירוב ל-1 − ln(2) ≈ 0.3068. ל-n = 100 הערך המדויק הוא ≈ 0.3118. הסימולציה מתקרבת למספר זה ככל שמספר הסיבובים גדל.

בונוס

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

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

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

⏳ טרם נשמר