חומות של תקווה (הסתברותית) במקום אפילוג

חיים שפירא | 388 במגירות . מהי האסטרטגיה הטובה ביותר העומדת לרשות האסירים ? * קודם כול ברור לגמרי שאם האסירים יערכו את החיפוש באופן אקראי, אין להם שום סיכוי להצליח במשימתם . 50 , שזה בעצם 100 100 האמת היא שיש סיכוי אך הוא שווה ל- 1 . אסביר : כל אסיר רשאי לפתוח 50 מתוך 100 המגירות 100 2 1 , ומפני האי-תלות בין ולכן הסיכוי שלו להצליח הינו 2 1 . כמה קטן 100 2 האסירים, הסיכוי להצלחת כולם שווה ל- מספר זה ? המחשבון שלי ( מיושן קצת ) רשם לי פשוט 0 . . . נאלצתי לבדוק במחשבונים שברשת וגיליתי שהסיכוי בקירוב טוב הינו : 8000000000000000000000000000000 . 0 ( התשובה המדויקת יותר היא 987000000000000000000000000000000 . 0 ) שזה בערך 0 . עם סיכוי הצלחה כזה אין שום סיבה לצאת לדרך — זוהי התאבדות . באופן מפתיע, ישנה אסטרטגיה שמזניקה את הסתברות ההישרדות של האסירים מ- 0 ( בערך ) ליותר מ- % 30 ! הנה האסטרטגיה : נזכור שלא רק האסירים, אלא גם המגירות ממוספרות מ- 1 עד 100 . * Anna Gál, Peter Bro Miltersen ) 2003 ( , " The cell probe complexity of succinct data structures ," Proceedings 30 th International Colloqu...  אל הספר