בתא יש אסיר, שמאוד רוצה לצאת לחופשי, ומגלה לפתע שיש 3 דלתות בתא. אם יבחר באחת הדלתות, הוא ימצא את עצמו במנהרה שבה יזחל במשך 3 שעות, שבסיומן… ימצא את עצמו שוב בתא. אם יבחר בדלת השנייה, הוא ימצא את עצמו במנהרה שבה יזחל במשך 5 שעות, שבסיומן – גם ימצא את עצמו שוב בתא. אבל אם יבחר בדלת השלישית, הוא ימצא את עצמו במנהרה שבה יזחל במשך 7 שעות, שבסיומן – יגיע אל החופש.
אז מה הבעיה? יש שתי בעיות. האחת היא שהוא אינו יודע איזו דלת מובילה לאן, ולכן בוחר באקראי בין 3 הדלתות. הבעיה השנייה היא שהאסיר סובל מבעיות זכרון, ובכל פעם שהוא מגיע לתא הוא שוכח באיזו דלת הוא בחר בעבר.
השאלה היא כמה זמן ייקח לו בממוצע עד שיגיע אל החופש, ולמה? מה תהיה התשובה אם יש n דלתות, והזמנים הם t1, t2,…,tn? וסעיף בונוס – מה השונות?
הערה: לחידה קוראים אמנם "דילמת האסיר", אבל אין קשר בינה לבין דילמת האסיר המפורסמת מתורת המשחקים. אז למה קוראים לה דילמת האסיר? כי זה שם נחמד וכי יש בה אסיר. ובנוסף, אולי זה יביא לאתר אורחים שמחפשים חומר על דילמת האסיר. לכן קוראים לחידה דילמת האסיר.
אתה שומר באבטחת ישובים, ואתה יודע שלקראת סוף השמירה עליך להעיר את חברך הטוב מוישה שישן בחדר מס' 3, כדי שיחליף אותך בשמירה. כשמגיע הרגע המיוחל, אתה נכנס לחדר מס' 3 כדי להעיר את מוישה, והנה… יש שם 3 חיילים ישנים! ומה הבעיה? כולם ישנים בתוך שקי השינה שלהם, מכוסים לגמרי, ואין לך שום דרך לדעת מי מהם זה מוישה! אתה יודע שלכולם היה יום מתיש, וממש לא היית רוצה להעיר את האיש הלא נכון, ושכל נגיעה בשק שינה של מישהו תעיר אותו בוודאות. בלית ברירה, אתה בוחר באקראי באחד החיילים, אבל רגע לפני שאתה מעיר אותו – קורה משהו: אחד משני החיילים האחרים מסתובב תוך כדי שינה, וכתוצאה מכך נחשפות פניו – מוישה הוא לא. והשאלה היא: האם תעיר את החייל שבחרת, או את החייל השלישי?
אם יש לכם שאלה או תגובה – רשמו אותה כאן