חידת אסירים

פורום לשאלות ודיונים כלשהם בענייני מתמטיקה.

חידת אסירים

הודעהעל ידי misparim » א' מאי 23, 2010 10:14 pm

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

 

Re: חידת אסירים

הודעהעל ידי costello » א' מאי 23, 2010 11:03 pm

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

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

 

Re: חידת אסירים

הודעהעל ידי צבי » א' מאי 23, 2010 11:21 pm

עכשיו תמצאו פתרון אם משנים את החוקים:
ספוילר: הצג
1. הסוהר יכול להכניס כל יום מספר כלשהו של אסירים (בזה אחר זה, כמובן).
2. מותר לאסיר לעשות כל פעולה על המתגים: לא ללחוץ על אף מתג, ללחוץ על מתג אחד או ללחוץ על שניהם.
3. כל האסירים חייבים לפעול לפי אותו אלגוריתם, כלומר אסור שהפעולה של אסיר תהיה מותנית בזהות של האסיר. לכל האסירים חייב להיות אותו תפקיד.
נערך לאחרונה על ידי צבי בתאריך ב' מאי 24, 2010 11:55 am, נערך פעם אחת בסך הכל.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי misparim » ב' מאי 24, 2010 12:03 am

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

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

יפה :thumbleft:

אגב, בתור מי שהיה בקורס החידות של רום פנחסי, אולי תחלוק עימנו כמה מהחידות שהיו שם? :mrgreen:
misparim

 

Re: חידת אסירים

הודעהעל ידי costello » ב' מאי 24, 2010 8:19 am

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


33 3 73 11 -
הייתי רק במפגשים הראשונים, אחר כך השעות התנגשו עם הסמינר של עמוס. מבין החידות שפתרתי, היפות נכנסו ל"מאגר" של החידות שאני שואל מדי פעם, וסביר שיגיעו גם לפורום הזה בהזדמנות. החידות שלא פתרתי עדיין מרוכזות על כמה דפים, אבל הן נשמרות ל"זמנים מתאימים".
costello

 

Re: חידת אסירים

הודעהעל ידי צבי » ב' מאי 24, 2010 11:52 am

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



לא... הפתרון צריך לעבוד גם אם הסוהר לא מודיע שכל יום הוא יכניס בדיוק אסיר אחד. ערכתי את ההודעה המקורית כדי להבהיר זאת.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי misparim » ב' מאי 24, 2010 1:59 pm

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

 

Re: חידת אסירים

הודעהעל ידי צבי » ב' מאי 24, 2010 2:07 pm

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


לא הבנתי...
ספוילר: הצג
מה זה אסטרטגיה סימטרית שבה אין לכל האסירים אותו תפקיד?
הכוונה היא שכל האסירים פועלים לפי אותו אלגוריתם, והאלגוריתם לא תלוי בזהות של האסיר. כלומר לא יכול להופיע באלגוריתם תנאי "אם אני אסיר X אני עושה כך, ואם אני אסיר Y אני עושה כך".
את יכולה לחשוב על זה כך: את פותרת את הבעיה בשביל האסירים - את מוצאת אלגוריתם, כותבת אותו על דף ושולחת לכל אסיר בדואר עותק של הדף, כאשר כל העותקים זהים. את לא יכולה לכתוב על הדף "אם אתה האסיר X תעשה כך" כי את לא מכירה את האסירים.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי misparim » ב' מאי 24, 2010 2:43 pm

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

 

Re: חידת אסירים

הודעהעל ידי צבי » ב' מאי 24, 2010 4:52 pm

33 3 73 11 כתב:
ספוילר: הצג
אסטרטגיה סימטרית היא כזאת שלמשל בשלב מסוים, אסיר שהמספר שלו הוא X מודולו 2 ירים את המתג ה-X. מהניסוח החדש שלך אני מניחה שאפשר להסיק שגם דבר כזה אי אפשר לעשות.


נכון, זה לא פתרון חוקי. כל האסירים זהים (אין להם מספרים או דבר אחר שמבדיל ביניהם) והם צריכים לפעול בדיוק לפי אותו אלגוריתם.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי Daniel » ו' מאי 28, 2010 8:16 pm

ידוע מה המצב ההתחלתי של המתגים?
Daniel
משתנה מקרי
 
הודעות: 36
הצטרף: ש' אפריל 24, 2010 3:02 am

Re: חידת אסירים

הודעהעל ידי misparim » ו' מאי 28, 2010 8:35 pm

לא.

אגב, אם כבר השרשור הוקפץ - לגבי הפתרון של קוסטלו:
ספוילר: הצג
תשומת ליבי הוסבה לעובדה שהפתרון בעצם לא נכון, כי יכול להיות שיכנס מישהו לפני המונה, והמונה לא יספור את השינוי שהנ"ל ביצע במפסק. הרעיון הוא כמובן נכון, אך צריך לציין שינוי קטן.
misparim

 

Re: חידת אסירים

הודעהעל ידי למינג בדרכים » ו' מאי 28, 2010 9:03 pm

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

ספוילר: הצג
הוא מניח שאסיר מס' 1 בכלל ייכנס לחדר מספר לא חסום של פעמים. מה מונע מהסוהר הסאדיסט להכניס את 1 ביום א', את 2 ביום ב' וכן הלאה, ובסופו של דבר להתקבע על להכניס רק את 23 לחדר שוב ושוב? זה הרג לי כל נסיון פתרון שחשבתי עליו. אפילו אם מניחים שהסוהר פועל על ידי הטלת קוביה, קיים סיכוי שמה שיקרה בפועל הוא הסיטואציה שאני מתאר, ואז מה יעשו האסירים?
לב טולסטוי (מלחמה ושלום) כתב:...ואנאטול, באותה עקשנות מיוחדת המצוייה באנשים מטומטמים לגבי מסקנה שהגיעו אליה בכוח שכלם שלהם, חזר על אותו שיקול הדעת, אשר כבר כמאה פעמים חזר עליו באוזני דולוחוב...
סמל אישי של המשתמש
למינג בדרכים
דוקטור דוצ'ה
 
הודעות: 36311
הצטרף: ג' אפריל 20, 2010 9:29 am

Re: חידת אסירים

הודעהעל ידי צבי » ו' מאי 28, 2010 9:38 pm

גדי צודק, הסתכלתי עכשיו במקור ממנו אני מכיר את החידה (ומשם לקחתי את חידת ההמשך) ושם כתוב שהסוהר חייב להכניס כל אסיר לחדר אינסוף פעמים.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי למינג בדרכים » ו' מאי 28, 2010 9:45 pm

זה משנה את הכל :angry:

אנא, הזהרו בניסוחים שלכם! אחרת נשסה בכם את מונטי הול. דברים כאלו הם כנראה הסיבה שבגללה עכשיו מלכלכים באינטרנט על ארדש כאילו הוא "לא הבין" את הפתרון של מונטי הול.
לב טולסטוי (מלחמה ושלום) כתב:...ואנאטול, באותה עקשנות מיוחדת המצוייה באנשים מטומטמים לגבי מסקנה שהגיעו אליה בכוח שכלם שלהם, חזר על אותו שיקול הדעת, אשר כבר כמאה פעמים חזר עליו באוזני דולוחוב...
סמל אישי של המשתמש
למינג בדרכים
דוקטור דוצ'ה
 
הודעות: 36311
הצטרף: ג' אפריל 20, 2010 9:29 am

Re: חידת אסירים

הודעהעל ידי misparim » ו' מאי 28, 2010 9:47 pm

זה (כלומר, הניסוח שהשתמשתי בו) הניסוח שבו סיפרו לי את החידה במקור 8-[
misparim

 

Re: חידת אסירים

הודעהעל ידי למינג בדרכים » ו' מאי 28, 2010 10:05 pm

ומה היה הפתרון? האם הוא התבסס (אולי במובלע) על ההנחה שכל אסיר נכנס לחדר אינסוף פעמים?
לב טולסטוי (מלחמה ושלום) כתב:...ואנאטול, באותה עקשנות מיוחדת המצוייה באנשים מטומטמים לגבי מסקנה שהגיעו אליה בכוח שכלם שלהם, חזר על אותו שיקול הדעת, אשר כבר כמאה פעמים חזר עליו באוזני דולוחוב...
סמל אישי של המשתמש
למינג בדרכים
דוקטור דוצ'ה
 
הודעות: 36311
הצטרף: ג' אפריל 20, 2010 9:29 am

Re: חידת אסירים

הודעהעל ידי צבי » ו' מאי 28, 2010 10:32 pm

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

הנה פתרון לגרסת המתג האחד (שכנ"ל מתאים גם לשני מתגים שניתן להבחין ביניהם):

ספוילר: הצג
האסירים ממנים את אליס לתפקיד המונה.
* אליס תמיד מעבירה את המתג למצב 1 (אם הוא כבר במצב 1 היא לא עושה כלום).
* כל אסיר אחר מעביר את המתג פעמיים למצב 0, כלומר אם כשהוא נכנס לחדר המתג במצב 1, והאסיר עדיין לא העביר אותו פעמיים למצב 0, האסיר מעביר אותו למצב 0.
* אליס סופרת כמה פעמים אחרי ביקורה הראשון היא מצאה את המתג במצב 0.
* כשהיא מגיעה למספר 43, היא מודיעה שכל האסירים היו בחדר.


תזכורת - באחת ההודעות למעלה נתתי גרסה למתקדמים, אני כותב אותה שוב עם תיקונים:

ספוילר: הצג
1. הסוהר יכול להכניס כל יום מספר כלשהו של אסירים (בזה אחר זה, כמובן).
2. יש שני מתגים. מותר לאסיר לעשות כל פעולה על המתגים: לא ללחוץ על אף מתג, ללחוץ על מתג אחד או ללחוץ על שניהם.
3. כל האסירים חייבים לפעול לפי אותו אלגוריתם, כלומר אסור שהפעולה של אסיר תהיה מותנית בזהות של האסיר. לכל האסירים חייב להיות אותו תפקיד.
4. בעקבות ההערה שלי לעיל, נתון נוסף שהפתרון שקראתי מניח אותו: כאשר האסירים מתכננים את האסטרטגיה שלהם הם יכולים לדבר על מתג ספציפי, למשל, הם יודעים מראש שיש מתג לבן ומתג שחור.
נערך לאחרונה על ידי צבי בתאריך ו' מאי 28, 2010 10:59 pm, נערך 2 פעמים בסך הכל.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי misparim » ו' מאי 28, 2010 10:52 pm

gadial כתב:ומה היה הפתרון? האם הוא התבסס (אולי במובלע) על ההנחה שכל אסיר נכנס לחדר אינסוף פעמים?

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


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

 

Re: חידת אסירים

הודעהעל ידי למינג בדרכים » ו' מאי 28, 2010 10:57 pm

בקשר לגרסה המתקדמת:
ספוילר: הצג
האם האסירים הם "חסרי זכרון", במובן זה שאסור שמה שאסיר עושה יושפע ממה שהוא ראה בעבר? או שהם יכולים להיות בעלי זכרון (ולכן בעצם להריץ אלגוריתמים שונים כתלות בזכרון שלהם).
לב טולסטוי (מלחמה ושלום) כתב:...ואנאטול, באותה עקשנות מיוחדת המצוייה באנשים מטומטמים לגבי מסקנה שהגיעו אליה בכוח שכלם שלהם, חזר על אותו שיקול הדעת, אשר כבר כמאה פעמים חזר עליו באוזני דולוחוב...
סמל אישי של המשתמש
למינג בדרכים
דוקטור דוצ'ה
 
הודעות: 36311
הצטרף: ג' אפריל 20, 2010 9:29 am

Re: חידת אסירים

הודעהעל ידי צבי » ו' מאי 28, 2010 11:01 pm

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


ספוילר: הצג
האסירים הם בעלי זכרון.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי למינג בדרכים » ו' מאי 28, 2010 11:04 pm

אה, וכמובן - האם ההנחה שכל אסיר מוכנס אינסוף פעמים עודנה תקפה?
לב טולסטוי (מלחמה ושלום) כתב:...ואנאטול, באותה עקשנות מיוחדת המצוייה באנשים מטומטמים לגבי מסקנה שהגיעו אליה בכוח שכלם שלהם, חזר על אותו שיקול הדעת, אשר כבר כמאה פעמים חזר עליו באוזני דולוחוב...
סמל אישי של המשתמש
למינג בדרכים
דוקטור דוצ'ה
 
הודעות: 36311
הצטרף: ג' אפריל 20, 2010 9:29 am

Re: חידת אסירים

הודעהעל ידי Daniel » ו' מאי 28, 2010 11:41 pm

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

(עריכה: רגע, הכוונה כאן לניסוח שבו מותר לשנות בדיוק אחד מהמתגים? אם כן אז xor לא תקף כמובן)
צבי כתב: הם יקבעו שהמתג השמאלי יתפקד כמו המתג היחיד? מי אמר שיש מתג שמאלי? :?
נערך לאחרונה על ידי Daniel בתאריך ו' מאי 28, 2010 11:47 pm, נערך פעם אחת בסך הכל.
Daniel
משתנה מקרי
 
הודעות: 36
הצטרף: ש' אפריל 24, 2010 3:02 am

Re: חידת אסירים

הודעהעל ידי Daniel » ו' מאי 28, 2010 11:44 pm

בגרסה המתקדמת יש הסתברות לטעות?
Daniel
משתנה מקרי
 
הודעות: 36
הצטרף: ש' אפריל 24, 2010 3:02 am

Re: חידת אסירים

הודעהעל ידי צבי » ש' מאי 29, 2010 5:33 pm

תשובות:
הסוהר עדיין חייב להכניס כל אסיר אינסוף פעמים.
אסור שתהיה טעות. הדרישה היא כמו בחידה המקורית: צריך למצוא אלגוריתם שלכל סדרת הכנסות שיקבע הסוהר (שמכניסה כל אסיר אינסוף פעמים) הוא יגרום בוודאות לאסיר כלשהו להודיע שכל האסירים היו בחדר, ולא תהיה הכרזה כזו לפני שכל האסירים אכן היו בחדר.
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3

Re: חידת אסירים

הודעהעל ידי צבי » ה' יוני 10, 2010 1:32 am

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

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

ספוילר: הצג
לכל אסיר יש שני משתנים פרטיים - s ו-t. אתחול:

קוד: בחר הכל
s := 2
t := 2


כל פעם שאסיר מוכנס לחדר, הוא פועל לפי האלגוריתם הבא:

קוד: בחר הכל
if t = 45 and R = 1
{
   announce "We Win!!!!!!!!!!!111"
   exit
}
if s = 2
{
   s := L
   toggle L
}
if s < 2 and s != L and R = 0
{
   toggle R
   t := t - 1
   if t = 0
   {
      s := 3
      toggle L
   }
}
if s = L and R = 1
{
   toggle R
   t := t + 1
}

אני מזכיר שוב מה האלגוריתם אמור לעשות: לכל סדרה של הכנסות אסירים לחדר שכוללת כל אסיר אינסוף פעמים, יהיה אסיר שיכריז "We Win!!!!!!!!!!!111", וההכרזה הזו תמיד תהיה לאחר שכל האסירים אכן היו בחדר.
נסו נא להסביר איך האלגוריתם הנ"ל פועל. אם לא תהיה הצלחה - תקבלו רמזים. :D
אָדָם יְלוּד אִשָּׁה קְצַר יָמִים וּשְׂבַע רֹגֶז
סמל אישי של המשתמש
צבי
מספר רציונלי
 
הודעות: 1832
הצטרף: ג' מאי 04, 2010 3:22 pm
מיקום: בין ב4 ל-ה3


חזור אל הפורום המתמטי

חזור אל הפורום המתמטי

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד