פורטל:מתמטיקה/חידות קשות/6

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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


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


חידת המשך 2: בנוסף לחידה הראשונה (הנורה בהתחלה כבויה), המלך מודיע למתמטיקאים כי הוא עלול לנסות לבלבל אותם ולשנות בעצמו מדי פעם את מצב הנורה - אך לא יותר מ-n פעמים. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?