למלך היו 100 מתמטיקאים בכלא. יום אחד הוא אסף אותם והכריז: "עד הלילה תהיו ביחד ותהיה לכם הזדמנות לגבש אסטרטגיה. לאחר מכן אשים כל אחד מכם בתא מבודד. בכל זמן שארצה אבחר מישהו באקראיות ואשים אותו בחדר שכל מה שיש בו זה נורה ומתג. מי שבפנים יוכל לשנות את מצב הנורה (אם היא הייתה דלוקה לכבות ואם כבויה להדליק) או לא לעשות כלום. בהתחלה הנורה תהיה כבויה. המטרה שלכם שבאחד הימים יבוא אלי מישהו ויגיד שכולם כבר היו בחדר לפחות פעם אחת. אם הוא יצדק, אשחרר את כולכם, אך אם יטעה, אוציא את כולכם להורג." מה צריכה להיות האסטרטגיה של המתמטיקאים?
הערה: לצורך החידה למתמטיקאים יש חיי אלמוות. כל אחד מהם נכנס מספר פעמים לא מוגבל לחדר, כלומר אין דבר כזה מישהו שנכנס בפעם האחרונה. כמו כן, אין המתמטיקאים יודעים את הזמנים בהם מוכנסים אנשים ואין הם יודעים את המספר הסידורי של כניסתם (בפרט הראשון שנכנס אינו יודע שהוא הראשון).
| פתרון
|
| על המתמטיקאים למנות ראש קבוצה. כל אחד מה-99 האחרים יפעל לפי האלגוריתם הבא: בפעם הראשונה שהוא רואה את הנורה כבויה, הוא מדליק אותה. בכל מקרה אחר, הוא לא עושה כלום. ראש הקבוצה פועל לפי האלגוריתם הבא: אם הנורה כבויה, הוא לא עושה כלום, ואם היא דלוקה, הוא מכבה אותה וסופר את מספר הפעמים שהוא מכבה. לאחר שכיבה 99 פעמים, בהכרח כולם כבר היו בחדר כי כל אחד הדליק פעם אחת ואף אחד לא כיבה.
|
|
חידת המשך: נניח ולא ידוע המצב בתחילתי של הנורה בחדר. כלומר ייתכן שלפני שהוכנסו המתמטיקאים היא הייתה דלוקה, וייתכן שהיא הייתה כבויה. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
| פתרון
|
| המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, רק שהפעם כל אחד מ-99 המתמטיקאים ידליק את הנורה הן בפעם הראשונה והן בפעם השנייה שהוא רואה אותה כבויה. ראש הקבוצה יספור הפעם עד 198. כך מובטח שאפילו אם הנורה הייתה דלוקה בהתחלה, וראש הקבוצה ספר אותה בטעות כמתמטיקאי, זה רק אומר שאחד המתמטיקאים הספיק להדליק את הנורה רק פעם אחת, ובכל מקרה כולם ביקרו בחדר.
|
|
חידת המשך 2: בנוסף לחידה הראשונה (הנורה בהתחלה כבויה), המלך מודיע למתמטיקאים כי הוא עלול לנסות לבלבל אותם ולשנות בעצמו מדי פעם את מצב הנורה - אך לא יותר מ-n פעמים. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
| פתרון
|
| המצב בו לא ידוע מצב הנורה ההתחלתי שקול לכך שהנורה בהתחלה כבויה, אך למלך מותר לשנות את מצבה פעם אחת. על כן המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, אלא שעל כל מתמטיקאי שאינו ראש הקבוצה להדליק את הנורה 1+n הפעמים שהוא רואה אותה כבויה, וראש הקבוצה יספור הפעם עד 99*(n+1). כך מובטח ש-n הפעמים בהם המלך התערב בתהליך לא גרמו לכלול בספירה מתמטיקאי שכלל לא נכח בחדר.
|
|