שם הקוד: אפור

[clocker]

שם הקוד: אפור

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

 

[עריסטו]

רמז וחידה נוספת

קוד גריי יאללה, איפה ה -

מה הקשר לחידת מגדלי האנוי?

 

[clocker]

קודם כל ../images/Emo25.gif

ואחרי זה

, לי באופן אישי אין מושג מה הקשר למגדלי הנוי - אבל אני אחשוב על זה

 

[carlos22]

הקטע

עם הרקורסיה ?

 

[עריסטו]

יותר מזה ../images/Emo58.gif

קוד גריי נותן לך ממש את הפתרון.

 

[1אברהם]

אולי

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

 

[עריסטו]

../images/Emo127.gif ועוד

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

 

[Werty123]

הפתרון שלי

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

0,2,4,6...2^N-2,2^N-1,2^N-3,2^N-5…3,1,0​

 

[1אברהם]

אבל איך הגעת לזה ש

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

 

[איייייל]

נראה לי שזה לא נכון

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

 

[Werty123]

סליחה../images/Emo128.gif

קבלו ביטול האבחנה לא נכונה בקריאה שנייה אני אחשוב על זה שוב