טוב - חידה חדשה

[guysoffer]

טוב - חידה חדשה

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

 

[Shaakedod]

שאלונת

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

 

[guysoffer]

אין רמאויות

רק מה שרשמתי - חייבים להזיז מתג אחד וזהו.

 

[Shaakedod]

אוקיי

בלי סימונים השאלה לא תתכן מפני שיש 4 מצבים 2 למעלה 2 למטה אחד למעלה שני למטה שני למעלה אחד למטה זה המצבים האפשריים... 4 מצבים מתוכם אין ייחוד או דרך ספציפית שמגיעה אפילו ל10 בלי לחזור על עצמה ! לכן משהונראה לי פה מסריח חחח

 

[guysoffer]

דווקא יש דרך, בלי רמאויות..

 

[Javali]

תשובה

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

 

[Shaakedod]

לא הבנתי איך

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

 

[Javali]

פשוט

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

 

[Shaakedod]

במקום להתנשא

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

 

[guysoffer]

תנסה לחשוב

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

 

[Javali]

מתנשא?

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

 

[guysoffer]

אכן - דומה לקודמת

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

 

[Javali]

שמתי לב

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

 

[guysoffer]

אכן.

 

[כלמנ]

שאלה

יש איזו מנורה מחוברת למתגים? מי רואה אותה?

 

[guysoffer]

אין שום דבר מחובר - המתגים לא עושים דבר

הם שם סתם בשביל החידה

 

[כלמנ]

נראה לי שיש לי...

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

 

[Javali]

יש עם זה בעיה קלה

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

 

[כלמנ]

אבל כולם יודעים שדודו הוא הראשון בבידוד...

מממ אני אנסה לפתור את זה...

 

[כלמנ]

לא בטוח שלזה התכוונת, אבל...

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