חידה

[doroni21]

חידה

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

 

[doroni21]

אין תגובה? מישהו?

 

[SymphonyX]

פתרון בינארי או משהו...

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

 

[the predator]

לא ראיתי אותך קודם אז...

נפתח בשרשור WELCOME!!!! ואם כבר היה שרשור כזה תתעלמו מההודעה הזו....

 

[doroni21]

נחמד

חשבתי גם אני על זה, אבל זה לא מסתדר עם נתוני השאלה.

 

[djdror]

../images/Emo35.gifשאלה לכותב החידה

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

 

[doroni21]

לא רלוונטי

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

 

[Belgarath]

לא ברור לגמרי ?

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

 

[doroni21]

הבהרה

האסירים אמורים לדעת להגיד מתי כולם כבר ביקרו בחדר המפסקים. הם לא אמורים לדעת מי היה כמה פעמים ומתי. הדבר היחידי שחשוב זה שכולם היו (כמו שכבר אמרתי יכול להיות שאסיר היה יותר מפעם אחת בחדר). האם זה יותר ברור עכשיו?

 

[djdror]

../images/Emo62.gif הפתרון שלי

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

 

[doroni21]

כל הכבוד ../images/Emo127.gif

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

 

[djdror]

אני לא הצלחתי לשכלל אותה לפתרון..

מלא. אבל אם אתה טוען שאפשר אז אני יחשוב על כך ביתר רצינות.

 

[doroni21]

סליחה סליחה

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

 

[pallidfool]

ככה לא צריך לדעת את המצב ההתחלתי:

במקום שכל אסיר מה-22 יסגור את המתג הימני רק פעם אחת, הוא יעשה זאת פעמיים. האסיר המנהיג לא יחכה לספור 22, אלא 43. כשהוא ספר 43, בהכרח 21 היו פעמיים ועוד אחד לפחות פעם אחת. כך, גם אם בהתחלה המתג היה מורם, ואסיר הוריד אותו, זו הפעם היחידה שהתבזבזה פעולה של אסיר והשיטה הנ"ל תעבוד.

 

[freedom rider]

למעשה צריך רק מתג אחד

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

 

[doroni21]

זה לא יתפוס

כי הטענה היא שהם צריכים לשנות את המתג כל פעם.