עריכת הדף "חידות" (פסקה)

== חידה 11 ==
שני אסירים וסוהר משחקים את המשחק הבא: לסוהר יש n מנורות. הוא מראה את המנורות לאסיר 1, ועובר עליהן בסדר לבחירתו. בכל פעם שהסוהר עובר למנורה הבאה, הוא שואל את אסיר 1 אם להדליק או לכבות אותה (האסיר רואה מי המנורה שהסוהר מצביע עליה). ככה המשחק ממשיך במשך n-1 מנורות, אבל במנורה האחרונה הסוהר מחליט בעצמו מה יהיה מצב המנורה.

בשלב הזה אסיר 1 יוצא ואסיר 2 נכנס לחדר, מסתכל על המנורות, וצריך לנחש מי הייתה המנורה האחרונה. אסיר 2 לא יוכל תמיד להצליח בניחוש אחד, אז נותנים לו k ניחושים.

הראו שאם k≥√n, האסירים יכולים לתאם אסטרטגיה שבה אסיר 2 בהכרח יצליח לנחש מי המנורה האחרונה.