חידת אסירים

[super]

../images/Emo35.gif חידת אסירים

1. בבית סוהר כלשהו ישנם מספר אסירים (מספרם ידוע להם ולסוהר). 2. בחדר הסוהר ישנו מפסק שיש לו שני מצבים On ו - Off. מצבו ההתחלתי של המפסק ידוע. 3. לסוהר רשימת אינסופית ואקראית לחלוטין של שמות האסירים, כאשר כל אסיר יכול להופיע יותר מפעם אחת (גם בסמיכות), אבל כל האסירים מופיעים לפחות פעם אחת. 4. בכל פרק זמן (משתנה ולא ידוע) קורא הסוהר לאסיר הבא מרשימתו. האסיר מגיע לחדרו של הסוהר, בוחן את המפסק, ומחליט האם לשנות את מצבו, אם לאו. 5. באיזשהו שלב, אחד האסירים שנכנס לחדר ורואה את מצב המפסק מצהיר כי כל האסירים ראו את המפסק לפחות פעם אחת. איך הוא יודע את זה

 

[Gaius Octavius]

שאלה.

כל האסירים שלפניו או כל האסירים בכלליות? כי אם זה לפניו זה קל נורא, זה אומר שהוא בטח השני והראשון שינה את זה.

 

[slallum]

כל האסירים שבכלא

כי אם זה היה כל האסירים שלפניו אז זה בטוח נכון לפי הנתונים של החידה

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

 

[גילי 69]

הוא יודע את זה ../images/Emo62.gif

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

 

[slallum]

../images/Emo128.gif

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

 

[Gaius Octavius]

מי אמר שזו נורה?

הוא אמר רק מפסק, למען האמת.

 

[super]

זה לא שיש לי את התשובה...

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

 

[djdror]

החידה בסדר גמור ויש פתרון.......

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

 

[slallum]

אז יש לנו 2 חידות P:

הראשונה היא החידה הזו =] והשניה היא - מה הנתון שהוסיפו בחידה הזו לעומת החידה של דרור עם ה-2 מפסקים?

 

[slallum]

ונראה לי שיש לי פתרון לחידה השנייה

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

 

[djdror]

אכן......

עלית על הנתון החדש שנתנו בחידה זו, ומכיוון שפתרת את החידה אהי חושב שאתה רשאי כבר לשנות את החתימה. אינך שוטה מופלג!!!!!

 

[pazro]

מה ששינו בחידה זו הוא ש

שאין על האסירים חובה לשנות משהוא כשהם נכנסים לחדר. בחידה השניה היוא שני מפסקים והיתה חובה על האסיר לשנות לפחות אחד מהם. נראה לי שהנוסח הזה יותר קל.

 

[גיאל]

זה כל הנתונים?

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

 

[slallum]

יש לי רעיון שמסתמך על זה שהאסירים

מדברים לפני זה.. אז זה לא הפתרון, אבל אולי זה יעזור לנו להגיע לפתרון

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

אז למישהו יש רעיון איך זה יכול להוביל אותנו לפתרון?

 

[גיאל]

זה בתנאי כמובן

שקוראים ליוסף אין סוף פעמים. אבל אם קוראים ליוסף פעם אחת בלבד, הפתרון לא נכון

 

[slallum]

הממ וואלה

אז אין לי שמץ

 

[Gaius Octavius]

וקוראים ליוסף אין-סוף פעמים,

מאחר והרשימה אין-סופית לכן ההסתברות שהוא לא יופיע בה עוד פעם היא אחד לאינסוף, ומאחר ו1 חלקי אינסוף זה אפס - הוא יופיע בה, כמו כל האסירים, אין-סוף פעמים.

 

[Gaius Octavius]

נשמע נכון -

לא נאמר שהאסירים לא מדברים זה עם זה. אול הייל עופר!

 

[djdror]

../images/Emo127.gifמצוין../images/Emo45.gif

זה הפתרון - ומישהו כבר הסביר לך למה זה בסדר. כל הכבוד!

 

[slallum]

מגניב ../images/Emo9.gif

עדיין הקטע של ההסתברות די מעצבן אותי, כי תמיד יכול להיות שזה לא יקרה.. אמנם ההסתברות שזה לא יקרה שואפת ל-0, אבל זה רק שואף ולא בטוח

טוב לדעת שצדקתי