מגדלי הָנוֹי

[בחשכת הלילה]

נתאר את המצבים (פוזיציות), המתקבלים במהלך משחק 'מִגְדְּלֵי הָנוֹי' עם שלושה מוטות ו-n דסקיות, לפי כמויות הדסקיות על המוטות, מבלי לפרט אילו דסקיות נמצאות על כל מוט. מצב הפתיחה הוא אֶן, אפס, אפס,
ומצב הסיום הוא אפס, אפס, אֶן.
מטרת המשחק היא להעביר את כל הדסקיות מהמוט הראשון אל המוט השלישי.

למשל, עבור n=3 המצבים הם:

(3,0,0)
(2,0,1)
(1,1,1)
(1,2,0)
(0,2,1)
(1,1,1)
(1,0,2)
(0,0,3)​

בדוגמה זו עבור n=3 אנו רואים שמצב (1,1,1) מופיע פעמיים, וכל אחד משאר המצבים – פעם אחת. מצב (0,1,2) אינו מופיע בכלל.

שאלה כללית: כמה פעמים מופיע מצב (a,b,c) עבור n דיסקיות (a+b+c=n)?

נסמן את התשובה לשאלה זו כ: (f(n,a,b,c. אמנם ארבעת המשתנים אינם בלתי תלויים, אבל כך נוח יותר לסמן, לדעתי. בדוגמה שלעיל:

f(3,3,0,0)=1
f(3,2,1,0)=0
f(3,2,0,1)=1
f(3,1,2,0)=1
f(3,1,1,1)=2
f(3,1,0,2)=1
f(3,0,3,0)=0
f(3,0,2,1)=1
f(3,0,1,2)=0
f(3,0,0,3)=1

​

עבור כל n, סכום כל ה-f שווה כמובן 2 בחזקת n.
יש גם נוסחת נסיגה כזאת:

f(n,a,b,c) = f(n-1,a-1,c,b) + f(n-1,b,a,c-1)​

(כאשר אחד או יותר מהמשתנים a,b,c שליליים, f(n,a,b,c) נחשב שווה 0).

כמו כן, די ברור ש: (f(n,a,b,c)=f(n,c,b,a.

עם זאת, עבור n "גדול מאוד" כל האמור לעיל אינו מספיק לחישוב f (עבור שלישיה כלשהי של a,b,c). יש רעיונות נוספים?

 

[עריסטו]

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

 

[בחשכת הלילה]

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

לאותה הדוגמה של n=3.

 

[בחשכת הלילה]

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

 

[בחשכת הלילה]

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

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