ערכתי לאחרונה בתאריך 08.09.03 בשעה 02:06 בברכה, dryice
יש לנו נורה, זה ביט אחד של מידע, זה וודאי לא יכול להיות
מונה, יש לנו 100 אסירים, האסירים נבחרים באקראי יתכנו חזרות,
ועל כן ספירת ימים נאיבית לא תועיל בפני עצמה,
הפתרון חייב להתבסס בין השאר על היכולת של אסיר לספור ימים.כאשר אסיר נכנס לחדר מה הוא יודע:
הוא יודע כמה ימים עברו.
הוא יודע כמה פעמים הוא עצמו נכנס לחדר בעבר.
הוא יודע מה מצב הנורה.
על סמך מידע זה באיזה שהוא שלב סופי אסיר צריך לדעת שכולם
עברו כבר. ועל סמך מידע זה, כל אסיר צריך לבחור את מצב הנורה
הבא.
אני חושד שפתרון וודאי של 100% הצלחה אין.
אבל אפשר להשיג איזה משהוא הסתברותי, של לדעת מתי בוודאות
גבוהה כרצוני כל האסירים בקרו בחדר.
ואולי דווקא יש איזה פתרון מוזר. שמתבסס על זה שלא בהכרח מייד
כשהאחרון נכנס הוא מזהה, אלא אולי קצת אחר כך.
ננסה להפריך:
בוא נניח שיש אסטרטגיה שעובדת, בעזרת האסטרטגיה הזאת יש מצב
כלשהוא שבוא עברו N ימים, הנורה במצב L והאסיר הנידון נכנס
לתא כבר K פעמים, והאסיר לפי האסטרטגיה ידע שכולם היו כבר.
כמובן שיש דרך לבחור אסירים כך שN וK יתקיימו ואילו לא כל
האסירים עברו, אבל הנורה מפריעה לנו.
אחשוב עוד אחר-כך.
האם ידוע ממקור מוסמך שהבעיה פתירה?
DRYICE
נ.ב
בעצם ידוע גם לאסיר שנכנס לתא, מספר סדורי שנתן לו.
כך שיתכן וההחלטה של שני אסירים במצב נתון תהיה שונה.
זה מוסיף למעשה המון, ומשכנע אותי שהחידה פתירה.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
