תנו בחידות...

[ש ב ו ז]

תנו בחידות...

ושלא יהיו קלות מידי

 

[DadleFish]

משהו ששאלו אותי פעם בראיון

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

 

[אופסשםמשתמש]

הגרסא המתקדמת אני שאלתי ועדיין לא ה

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

 

[DadleFish]

זה כנראה אפשרי -

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

 

[yoniBLA]

האם התשובה היא

8 סיבובים?

 

[IP yuval]

לא. סיימת כבר את הקורס או שאתה סתם

בחופש?

 

[yoniBLA]

טירונות ביום רביעי ../images/Emo13.gif

 

[IP yuval]

../images/Emo50.gif ../images/Emo13.gif

 

[ש ב ו ז]

פתרון (נדמה לי):

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

 

[DadleFish]

לא הבנתי את האלגוריתם,

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

 

[DadleFish]

התשובה היא X לחיצות. מה האלגוריתם?

 

[yoniBLA]

ממה שאני הבנתי...

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

 

[DadleFish]

תנסה ותראה

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

 

[yoniBLA]

טוב....

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

 

[DadleFish]

בוא נגיד ככה

מספר הנסיונות נכון. עכשיו תוכיח למה הפתרון שלך עובד.

 

[ש ב ו ז]

"תשובה רצינית"

תוך 8 לחיצות על הזמזם. הינה הסבר מפורש למי שלא הבין מהתשובה הקודמת. נסמן את המטבעות 1,2,3 ו4 (הם מסודרים באופן מעגלי כך ש 1=4+1 ונתעלם מהרוטציה כי אפשר לשקלל אותה) שלב א': 1.לחץ על הזמזם 2.עבור I מ1 עד 3 בצע 2.1 הפוך מטבעות(I+1,I) 2.2 לחץ על הזמזם {הערה אם המצב התחילי היה 2 מכל סוג הרמקול ינגן. מכיוון שאם זוג המטבעות בזוג שונים הוא "יתיישר" לאחר שני מהלכים מכיוון שאחד יתהפך פעמיים ואחד יתהפך פעם אחת בלבד. דוגמה: 1-לבן,2-שחור,3-שחור,4-לבן הפוך(1,2). מתקבל 1-שחור,2-לבן,3-שחור,4-לבן הפוך(2,3). מתקבל 1-שחור,2-שחור,3-לבן,4-לבן ניתן לראות כי הזוג 1,2 התיישר מהסיבה הנ"ל. הזוג 3 ייתישר במהלך הבא כי הפיכה אחת מתוך שתיים דרושות כבר נעשתה(2,3) אם יש שניים מאותו הסוג הרמקול ינגן במהלך הראשון.) שלב ב: הפוך(1) בצע שלב א, זהו. גם הפתרון של יוני נכון.

 

[ש ב ו ז]

סה"כ 3+1+3+1 נסיונות.

 

[DadleFish]

לא לקחת בחשבון את הסיבוב

הנה לפי הדוגמה שלך לגבי זוג: 1-לבן, 2-שחור, 3-שחור, 4-לבן הפוך 1,2: 1-שחור, 2-לבן, 3-שחור, 4-לבן אבל אז יש סיבוב, ולכן: 1-לבן, 2-שחור, 3-לבן, 4-שחור הפוך 2,3+סיבוב: 1-שחור, 2-לבן, 3-לבן, 4-שחור הפוך 3,4+סיבוב: 1-לבן, 2-שחור, 3-לבן, 4-שחור בשום מצב פה לא קיבלת זמזום.

 

[yoniBLA]

הסבר

כמו שאמרתי קודם, אנחנו מתעלמים מהקטע של הסיבוב, כי הוא לא באמת משפיע על כלום ומתייחסים לזה כאל 4 מטבעות. אחד נשאר קבוע במצב ההתחלתי שלו, ועם השאר אנחנו רוצים לעבור על כל האפשרויות. כדי לעשות את זה, בכל פעם נשנה את המצב של מטבע אחר, במעין זיגזגים... משהו כזה (F = מטבע שהופכים): Fxxx צ xFxx צ xxFx צ xFxx ד Fxxx צ xFxx צ xxFx צ

 

[DadleFish]

בוא נראה

0100 הוא המצב ההתחלתי, ואני עושה את הצעדים שלך: הפיכה של א': 1100 (הפיכה), 1001 (סיבוב) הפיכה של ב': 1101 (הפיכה), 1011 (סיבוב) הפיכה של ג': 1001 (הפיכה), 0011 (סיבוב) הפיכה של ב': 0111 (הפיכה), 1110 (סיבוב) הפיכה של א': 0110 (הפיכה), 1100 (סיבוב) הפיכה של ב': 1000 (הפיכה), 0001 (סיבוב) הפיכה של ג': 0011 (הפיכה), 0110 (סיבוב) אם אין לי טעות, לא הצלחת. חוץ מזה, בוא נניח שהאלגוריתם שלך עובד - למה שיעבוד? למה אתה חושב שהסיבוב "לא באמת משפיע על כלום"?